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

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

если это код для хвостовой рекурсии или итеративного Фибоначчи:

(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)

Благодарность!


fibonacci scheme
person Sarah    schedule 28.09.2014    source источник
comment
(define (fib n) ;определить функцию fib и переменную n не совсем так -- это определяет функцию fib, которая принимает один параметр с именем n. Аналогично, (define (fib-iter ... определяет функцию fib-iter, которая принимает 3 параметра, 1 – a, 2 – b и 3 – count. Чтобы наглядно представить, как работает хвостовая рекурсия, нарисуйте две горизонтальные линии над и под формой (fib-iter a b count). У вас получится фрейм – именованный блок с три слота (в данном случае).Затем каждый вызов (fib-iter x y z) просто помещает три значения x y z в три слота кадра и (повторно) начинает свое выполнение.   -  person Will Ness    schedule 29.09.2014

Ответы (2)


arrow_upward
4
arrow_downward

В процедуре 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, использующий явную конструкцию цикла и те же самые имена переменных. Это эквивалентно реализации Scheme:

def fib(n):
    count = n
    a, b = 1, 0
    while count != 0:
        a, b = a + b, a
        count = count - 1
    return b
person Óscar López    schedule 28.09.2014
comment
Не понимаю, почему бы и нет (fib-iter 0 1 n) - person Sarah; 29.09.2014
comment
Большое спасибо! Я наконец-то могу обдумать это - person Sarah; 29.09.2014
comment
@Sarah Было бы так, если бы fib-iter было написано немного по-другому, например, (if (zero? count) a (fib-iter b (+ a b) (- count 1))). Но в вашем случае роли a и b поменялись местами с их обычными значениями. - person Chris Jester-Young; 29.09.2014

arrow_upward
2
arrow_downward

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

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

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

Добавление оператора print к 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)`
person uselpa    schedule 28.09.2014