Рекурсия

Рекурсия – это такой способ организации вычислительного процесса, при котором процедура или функция в ходе выполнения составляющих ее операторов обращается сама к себе.

Пример. Вычислить n! (факториалом натурального числа n называют произведение чисел 1*2*3*4*…*n). Число n вводится с клавиатуры.

После запуска программы на экран выводится сообщение «Введите целое число N < 20», затем с клавиатуры считывается значение целого числа N и в выражении F:=Faktorial(N) вызывается функция Faktorial с параметром-значением N. В подпрограмме-функции вычисления факториала проверяется условие N=1. Если оно выполняется, то имени функции Faktorial присваивается значение 1, на этом выполнение подпрограммы завершается. Если условие N=1 не соблюдается, то выполняется вычисление произведения N*Faktorial(N-1). Вычисление произведения носит рекурсивный характер, т. к. при этом осуществляется вызов функции Faktorial(N-1), значение которой вычисляется, в свою очередь, через вызов функции Faktorial(N-2), которая также будет вызывать функцию Faktorial(N-3), и т. д. до тех пор пока значение формального параметра N не станет равным 1. Т. к. базовая часть описания рекурсивной функции Faktorial определяет значение Faktorial=1 для N=1, то рекурсивные вызовы функции больше не выполняются, а наоборот, выполняется вычисление функции Faktorial для чисел, возрастающих от 1 до N, причем функция Faktorial всякий раз возвращает значение, равное произведению очередного k-ого числа на факториал от (k-1)-ого числа. Последнее возвращение результата вычисления функции Faktorial присвоит переменной F значение произведения всех чисел от 1 до N, т. е. факториал числа N.

Использование рекурсии обычно выглядит более изящно, чем итерационная, и дает более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение оперативной памяти компьютера.