Технический форум

Технический форум (http://www.tehnari.ru/)

- Помощь студентам (http://www.tehnari.ru/f41/)

- - Рекурсия (http://www.tehnari.ru/f41/t48600/)

Рекурсия

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

Код:

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 (Сообщение 482224)

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

вы о чем??

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

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

ОБЯЗАТЕЛЬНО условие выход из рекурсии
Тело рекурсии
Вызов этой же функции опять.
если "разложить" код приведенный выше для функции 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