|
Рекурсия
|
|
| Fess | Дата: Среда, 29.05.2013, 12:26 | Сообщение # 1 |
|
Добрый админ
Сообщений: 2339
Статус:  | Рекурсия
Данная программа несколько раз решает две функции, каждое последующее решение основано на результате прошлого решения. Это и есть рекурсия. Зная первый член последовательности мы можем найти любой последующий член. Далее описан сложный пример рекурсии:
Код 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 ...
|
| |
| |
| bestervuld | Дата: Четверг, 30.05.2013, 19:48 | Сообщение # 2 |
|
Группа: Удаленные
| Всё чётко, и понятно. 
|
| |
| |
| DarthVader | Дата: Суббота, 01.06.2013, 18:47 | Сообщение # 3 |
|
Группа: Удаленные
| Вот, кстати, классический пример реализации функции факториала с использованием рекурсии. Всё "мясо" кода составляет всего один оператор:
Код function fact (n : integer) : longint;
BEGIN
if n <= 1 then fact := 1
else fact := n * fact (n - 1);
END;
Сообщение отредактировал DarthVader - Суббота, 01.06.2013, 18:49 |
| |
| |
| Fess | Дата: Суббота, 01.06.2013, 19:11 | Сообщение # 4 |
|
Добрый админ
Сообщений: 2339
Статус: | Уважаемый DarthVader, that's interesting (:
|
| |
| |
| Black_Gamer79 | Дата: Суббота, 18.01.2014, 17:34 | Сообщение # 5 |
|
Сообщений: 2
Статус: | И тут я понял, что такое "последовательность Фибоначчи" хД.
Спасиб.
|
| |
| |
| TEXHIK | Дата: Суббота, 01.03.2014, 04:43 | Сообщение # 6 |
|
Сообщений: 1
Статус: | То что ты описал это не совсем рекурия, это.... это нечто не имеющее названия) А рекурсией называется объект, состоящий из самого себя. (Все фракталы - рекурсивные объекты).
В программировании же рекурсией называется функция, вызывающая саму себя, пример который правильно привел DarthVader. А у тебя просто цикл, это не рекурсия, так что не вводи людей в заблуждение.
Кстати, ще одна из функций, которую удобно вычислять рекурсивно - степень, на нормальных языках в которых присутствует тренарный оператор это будет выглядеть так:
Код public int power(int a, int b){
return b>0?a*power(a,b-1):1;
}
|
| |
| |
