recursion - スキームにおけるフィボナッチ

Question

私は、Scheme で再帰を理解しようとしていますが、単純なフィボナッチ数の問題など、予行演習を行うのに苦労しています。

誰かが私のために、追加が行われるステップを分解できますか?

(define (fib n)
  (if (<= n 2)
      1
      (+ (fib (- n 1)) (fib (- n 2)))))

Answer 1

タグが示すように、Racket を使用している場合は、ステッパーが組み込まれています。

プログラムを DrRacket に入力し、右上のメニューで [ステップ] をクリックします。

すると、ステッパー ウィンドウが開きます。[ステップ オーバー アンド オーバー] をクリックすると、プログラムの実行をウォークスルーできます。

ステップ数をもう少し管理しやすくしたい場合は、実行をトレースするために 10 未満の数を選択してください。

Answer 2

疑似コードでは、=> ( 1 1 2 3 5 ... ) です。fib(n) = n <= 2 -> 1 ; else -> fib(n-1) + fib(n-2)

たとえば、次のようにfib(5)削減されます。

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + fib(3)
((fib(2) + fib(1)) + fib(2)) + fib(3)
((1 + 1) + fib(2)) + fib(3)
(2 + fib(2)) + fib(3)
(2 + 1) + fib(3)
3 + fib(3)
3 + (fib(2) + fib(1))
3 + (1 + 1)
3 + 2
5