Рекурсия

[Gagarin614]

Рекурсия

Помогите написать программу в делфи:
Условие:
Описать рекурсивную функцию
function fib(n : integer) : integer;
для вычисления n-ого (n =< 40) числа Фибоначчи.
Указание.
Последовательность чисел Фибоначчи fk образуется так:
f0=1, f1=1, fk = fk-2 + fk-1.
Зарания спасибо

 

[kreol]

function fib(n:integer): integer;
begin
  if (n = 0) or (n = 1) then
   fib := 1;
  else  
   fib := fib(n - 1) + fib(n - 2);
end;

вроде так.
п.с. счет идет с 0
т.е.
0 -1
1 -1
2 -2
3 -3
4 -5
5 -8 и т.д.
хотя в lisp -e это намного изящнее

(defun fibonacci(n)
    (if (or (= n 0) (= n 1))
     1
     (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))

 

[Gagarin614]

примного лагодарен, не могли бы пояснить что выполняет каждая строчка, встречаюсь с этой прроцедурой впервые

 

[kreol]

встречаюсь с этой прроцедурой впервые

вы о чем??

 

[Gagarin614]

о том что тему рекурсия с трудом понимаю

 

[kreol]

ааа ну рекурсия это вызов функции самой себя некоторое количество раз.
общий принцип построения:

ОБЯЗАТЕЛЬНО условие выход из рекурсии
Тело рекурсии
Вызов этой же функции опять.
если "разложить" код приведенный выше для функции fib(3) то получим

"переменной" - "функции" после первого прохода возвращается
fib(3-1)+ fib(3 - 2) т.е. fib(2)+fib(1) после второго прохода
fib(2) переходит в fib(1) - fib(0) a fib(1) просто в 1
дальше
fib(1) -> 1 fib(0)-> 1 ну и 1
в общем у нас получается 3
проверяем
№ 0 1 2 3
числа фиб. 1 1 2 3
как видим мы посчитали реально не для 3-го элемента а для 4-го т.к. номера элементов начинаются с 0

 

[Gagarin614]

Спасибо