Объяснение хвостовой рекурсии Фибоначчи по схеме?

Я пытался понять хвостовую рекурсию в схеме, и я с трудом понимая, что происходит в движении к примеру, используя хвост рекурсию Фибоначчи ...Объяснение хвостовой рекурсии Фибоначчи по схеме?

если это код хвостовую рекурсию, или итерационные Фибоначчи:

(define (fib n) 
    (fib-iter 1 0 n)) 

(define (fib-iter a b count) 
    (if (= count 0) 
    b 
    (fib-iter (+ a b) a (- count 1))))

я могу по существу понять, что происходит в каждой строке за исключением здесь:

(fib-iter 1 0 n))

, что на самом деле происходит в этой строке? Я не могу найти объяснения нигде. Я новичок в Scheme, и синтаксис до сих пор довольно запутан.

Или может кто-нибудь объяснить, что происходит в каждой строке? это мое основное понимание, но я не уверен, если я прав:

(define (fib n) ;;define the function fib and variable n 
    (fib-iter 1 0 n)) ;;?? no idea 

(define (fib-iter a b count) ;;define function fib-iter, variables a, b and count 
    (if (= count 0) ;;if the count is equal to 0, 
    b ;;return b 
    (fib-iter (+ a b) a (- count 1)))) ;;recursively calling function fib-iter with 3 parameters (a+b), a and (count - 1)

спасибо!

источник

2014-09-28 Sarah

«(определить (FIB п), определим функцию выдумку и переменную п» не совсем так - это * определяет функцию 'fib', которая принимает один параметр под названием' n' *. Аналогично, '(define (fib-iter ...' определяет функцию 'fib-iter', которая принимает 3 параметра, 1-й по имени' a', 2nd «' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' ' поле с тремя слотами (в этом случае). Затем каждый вызов '(fib-iter xyz)' просто помещает три значения 'xyz' в три слота frame и (re) начинает выполнение. –

Там опечатка в fib процедуре (открытие скобки отсутствует), она должна быть определена следующим образом:

(define (fib n) 
    (fib-iter 1 0 n))

Сказав, что итерационный fib процедура использует помощник под названием fib-iter для осуществления фактического итерация. Эта строка:

(fib-iter 1 0 n)

Просто называет помощника в первый раз. Как известно, серия фибоначчи начинается со значений 0 для n=0 и 1 для n=1, и это именно те значения, которые мы передаем как параметры, для запуска цикла итерации вместе со значением n, которое представляет собой число итераций мы хотим сделать до остановки.

С этого момента, a будет содержать значение Фибоначчи n-1 и b будет содержать значение Фибоначчи для n-2, и каждый последующий шаг в итерации не заботится об обновлении переменных a и b соответственно, до тех пор, n является ноль, и в этот момент мы останавливаем и возвращаем результат.

Возможно, было бы проще представить, что происходит, если мы напишем тот же алгоритм в императивном стиле. Вот один пример в Python, используя явную конструкцию цикла и те же имена переменных. Это эквивалентно реализации Схемы:

def fib(n): 
    count = n 
    a, b = 1, 0 
    while count != 0: 
     a, b = a + b, a 
     count = count - 1 
    return b

источник

2014-09-28 21:43:15

Я не понимаю, почему этого не будет (fib-iter 0 1 n) – Sarah

Большое вам спасибо! Я могу, наконец, обернуть вокруг себя – Sarah

@Sarah Было бы, если бы 'fib-iter' были написаны немного иначе, например' (if (zero? Count) a (fib-iter b (+ ab) (- count 1))) '. Но в вашем случае роли 'a' и' b' были заменены их обычными значениями. –

В коде есть ошибка; fib должна быть процедура:

(define (fib n) 
    (fib-iter 1 0 n))

Что делает это вызывает fib-iter с начальными значениями а (= 1), Ь (= 0) и считать (= число Фибоначчи вы хотите, что является формальным параметр n - fib).

Добавление печати «о» на fib-iter показывает, что происходит, в этом примере для (fib 7):

a=1 b=0 count=7 ; initial values as given by `fib` 
a=1 b=1 count=6 
a=2 b=1 count=5 
a=3 b=2 count=4 
a=5 b=3 count=3 
a=8 b=5 count=2 
a=13 b=8 count=1 
a=21 b=13 count=0 
13 ; the returned value for `(fib 7)`

источник

2014-09-28 21:43:29 uselpa

Объяснение хвостовой рекурсии Фибоначчи по схеме?

ответ

Смежные вопросы