Wie finde ich Fibonacci-Zahlen in Scheme?

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

nahm ich diesen Code aus dem SICP Buch, aber ich bin verwirrt. Ich verstehe die Idee des Fibonacci-Algorithmus vollständig, aber dieser Code hat mich aufgehalten. Was genau macht die letzte Zeile? Als Antwort, wenn ich versuche, eine fib (5), sollte ich 0,1,1,2,3,5 bekommen, aber die Logik scheint seltsam.

Answer 1

Das Verfahren implementiert die Fibonacci-Serie als iterativen Prozess. In diesem Fall ist fib die Hauptprozedur, die fib-iter aufruft, was die eigentliche Arbeit mittels einer Iteration erledigt. Beachten Sie, dass count wird verwendet, um die Anzahl der Iterationen zu steuern wir wollen, während a und b werden verwendet, um die Ergebnisse der Fibonacci-Reihe zu speichern für n-1 und n-2 sind. Die Zeile (fib-iter (+ a b) a (- count 1)) bringt die Iteration auf die nächsten Werte.

Bitte nehmen Sie sich die Zeit, um über iterative vs. rekursive Prozesse im Buch zu lesen, lesen Sie auch über Tail Recursion - das sind die Konzepte, die Sie verstehen müssen, um wirklich zu verstehen, was im Beispiel passiert.

Zum Vergleich wollen wir sehen, wie die gleichen Verfahren aussehen würde eine herkömmliche Syntax (Python) mit:

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 

Wie Sie sehen, die fib_iter Prozedur einfach über einen Bereich von Werten Iterieren durch die count gesteuert Variable, die a und b den nächsten Werten in der Reihe zuweist, bis eine Anzahl von Iterationen abgeschlossen ist; An diesem Punkt ist das Ergebnis in b und wird zurückgegeben.