Теория:
Рекурсия — это функция, которая обращается сама к себе.
Описание рекурсии происходит так же, как и описание обычной функции.
Напишем программу, которая будет выводить на экран числа Фибоначчи до указанного элемента.
Вспомним: числа Фибоначчи — это числовой ряд, где каждый последующий элемент получается путём сложения двух предыдущих.
Ряд Фибоначчи:
Опишем рекурсивную функцию.
function Fib (N: integer): integer;
begin
if (N: \(=\) \(1\)) or (N: \(=\) \(2\)) then
Fib: \(=\) \(1\)
else Fib: \(=\) Fib (N \(-\) \(1\)) \(+\) Fib (N \(-\) \(2\));
end;
Если порядковый номер числа \(1\) или \(2\), то мы указываем, что они равны единице. Вычисление остальных чисел Фибоначчи записываем после else: сумма двух предыдущих чисел.
Рекурсивная функция работает по нисходящему и восходящему принципу.
Чтобы вычислить \(10\)-й элемент последовательности функции, нужно знать значения \(9\)-го и \(8\)-го элементов, потому что:
\(F (10) = F(9) + F(8)\);
\(F (9) = F(8) + F (7)\);
\(F (8) = F(7)+F(6)\) и т. д., пока функция не дойдёт до самого первого элемента, после чего будет подниматься вверх и складывать все получившиеся числа.
Источники:
Изображения. © ЯКласс.