Рекурсия
Данная программа несколько раз решает две функции, каждое последующее решение основано на результате прошлого решения. Это и есть рекурсия. Зная первый член последовательности мы можем найти любой последующий член. Далее описан сложный пример рекурсии:
Код
program bb;
var
F,Q: array [-100..100] of integer;
n:integer;
begin
F[1]:=1;
Q[1]:=1;
for n:=2 to 20 do
begin
F[n]:=F[n-1]+2*Q[n-1];
Q[n]:=-2*F[n-1]+Q[n-1];
writeln('F[',n,']:= ',F[n-1],' + ',2*Q[n-1],' = ',F[n]);
writeln('Q[',n,']:= ',-2*F[n-1],' + ',Q[n-1],' = ',Q[n]);
end;
end.
Ярким (и более простым) примером рекурсии является также последовательность Фибоначчи - это последовательность цифр, в которой каждая следующая цифра равна сумме двух предыдущих. Вот эта последовательность:
1 1 2 3 5 8 13 21 34 55 ...
Формула последовательности Фибоначчи : F[n]:=F[n-1] + F[n-2] , при этом F[1]:=1; F[2]:=1;
Код
program bb;
var
F: array [-100..100] of integer;
n:integer;
begin
F[1]:=1;
F[2]:=1;
for n:=3 to 20 do
begin
F[n]:=F[n-1] + F[n-2];
writeln('F[',n,']:= ',F[n-1],' + ',F[n-2],' = ',F[n]);
end;
end.
Прогрессии
В школьном курсе математики рассматриваются такие вещи, как арифметическая и геометрическая прогрессии. Так вот, это тоже своего рода рекурсии. Формула арифметической прогрессии (x <> 0):
F[n]:=F[n-1] + x;
Пример арифметической прогрессии, в которой каждый раз мы будем прибавлять 3 (формула F[n]:=F[n-1] + 3; F[0]:=0;)
0 3 6 9 12 15 18 21 24 ...
Формула геометрической прогрессии (x > 0):
F[n]:=F[n-1]*x;
Пример геометрической прогрессии, в которой каждый раз мы будем умножать на 2 (формула F[n]:=F[n-1] * 2; F[0]:=1;)
1 2 4 8 16 32 64 128 256 ...
