私は、Scheme で再帰を理解しようとしていますが、単純なフィボナッチ数の問題など、予行演習を行うのに苦労しています。
誰かが私のために、追加が行われるステップを分解できますか?
(define (fib n)
(if (<= n 2)
1
(+ (fib (- n 1)) (fib (- n 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