Как найти числа Фибоначчи в Схеме?

Question

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

Я взял этот код из книги SICP, но я в замешательстве. Я полностью понимаю идею алгоритма Фибоначчи, но этот код заставил меня застрять. Что именно делает последняя строка? В качестве ответа, если я пытаюсь оценить фиб (5), я должен получить 0,1,1,2,3,5, но логика кажется странной.

Answer 1

Процедура реализует ряд Фибоначчи как процесс итеративный. В этом случае fib является основной процедурой, которая вызывает fib-iter, что делает фактическую работу с помощью итерации. Обратите внимание, что count используется для управления количеством желаемых итераций, тогда как a и b используются для хранения результатов серии Фибоначчи для n-1 и n-2 соответственно. Строка (fib-iter (+ a b) a (- count 1)) продвигает итерацию к следующим значениям.

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

Для сравнения, давайте посмотрим, как одни и те же процедуры, будет выглядеть с использованием более обычного синтаксиса (в Python):

def fib(n): 
    return fib_iter(1, 0, n) 

def fib_iter(a, b, count): 
    while count != 0: # same as asking `(if (= count 0) ...)` 
    a, b = a + b, a # same as passing `(+ a b) a` to recursive call 
    count -= 1  # same as `(- count 1)` 
    return b   # same as returning `b` at end of recursion 

Как вы видите, fib_iter процедура просто итерация диапазон значений контролируемых count переменную, присваивая a и b следующим значениям в серии, вплоть до завершения ряда итераций; на данный момент результат получается в b и возвращается.