Этейн была на минном поле, окруженная людьми, которые не могли оттуда уйти, и некоторые из них истекали кровью до смерти от тяжёлых ран. Их крики переворачивали ей душу. Говорят, что раненые солдаты зовут маму, но у клонов не было матери. Они звали своих братьев…
Во время бойни на Квиилуре
Карен Тревисс, "Истинное лицо"





Сколько глобус ни крути, там Fess-Style не найти...
Сайт Fess'a » Рекурсия - Форум
[ Новые сообщения · Участники · Правила форума · Поиск ]
Страница 1 из 11
Форум » Программирование » Паскаль » Рекурсия (Что же такое рекурсия?)
Рекурсия
FessДата: Среда, 29.05.2013, 12:26 | Сообщение # 1

Добрый админ
Сообщений: 2338
Статус:
Рекурсия

Данная программа несколько раз решает две функции, каждое последующее решение основано на результате прошлого решения. Это и есть рекурсия. Зная первый член последовательности мы можем найти любой последующий член. Далее описан сложный пример рекурсии:

Код
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 ...
Прикрепления: 6542017.png(8Kb) · 2171722.png(8Kb)
 
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;
Такая функция прописывается после var'а и перед begin'ом программы. И если в тексте нужно посчитать факториал, допустим, числа a, то просто пишем:
Код
b := fact (a);


Сообщение отредактировал DarthVader - Суббота, 01.06.2013, 18:49
 
FessДата: Суббота, 01.06.2013, 19:11 | Сообщение # 4

Добрый админ
Сообщений: 2338
Статус:
Уважаемый 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;
}
 
Форум » Программирование » Паскаль » Рекурсия (Что же такое рекурсия?)
Страница 1 из 11
Поиск: