Числа Фибоначчи (Fibonacci numbers) можно рекурсивно определить с помощью следующих формул:
Fib(O) = 0
Fib(l) = 1
Fib(N) = Fib(N — 1) + Fib(N — 2 ) для N>1.
Третье уравнение дважды использует функцию Fib рекурсивно, один раз со
значением N — 1 и один раз со значением N — 2. В данном случае необходимо иметь
два граничных значения для рекурсии: Fib(0) — 0 и Fib(l) = 1. Если задать только
одно из них, рекурсия может оказаться бесконечной. Например, если установить
только Fib(0) — 0, то вычисление Fib(2) будет выглядеть следующим образом:
Fib(2) = Fib(l) + Fib(O)
= [Fib(O) + Fib(-l)] + 0
= 0 + [Fib(-2) + Fib(-3)]
= [Fib(-3) + Fib(-4)] + [Fib(-4) + Fib(-5)]
И т.д.
Данное определение чисел Фибоначчи легко преобразовать в рекурсивную
функцию:
function Fibo(n : Double) : Double;
begin
if (n Fibo := n
else
Fibo := Fibo(n — l)+Fibo(n — 2) ;
end;