Рекурсия. Рекурсивным называется объект, который частично определяется через самого себя

Рекурсивным называется объект, который частично определяется через самого себя. Рассмотрим функцию n!

n!:= 1 * 2 * 3 *..* n;

Такое произведение можно вычислить с помощью интерактивных циклических конструкций.

f:=l;

for i:=l to n do f:= f * i;

Однако существует другое определение факториала, в котором используется рекуррентная формула. Тогда, факториал определяется следующим образом:

1. 0! = 1;

2. для любого n > 0 n! = n* (n-1)!;

Организация вычисления по рекуррентным формулам можно и без использования рекурсий. Однако при этом встаёт вопрос о качестве программы и доказательстве её эквивалентности формы.

Использование рекурсии позволяет почти дословно запрограммировать вычисление по рекуррентным формулам.

Так, прямая формула чисел Фибоначчи:

1. F(1)=l;

2. F(2)=l;

3. для любого n > 0 F(n) = F(n-l) + F(n-2);