recursion - 计划中的斐波那契

Question

我试图理解 Scheme 中的递归，我很难为它做空运行，例如一个简单的斐波那契数问题。

有人可以为我分解添加发生的步骤吗？

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

Answer 1

如果您使用的是 Racket，如您的标签所示，那么您有一个内置的步进器。

在 DrRacket 中输入程序，点击右上角菜单中的 Step：

然后将打开一个步进窗口。单击 Step over and over，您可以遍历程序的执行过程。

如果您希望步骤数更易于管理，请选择一个小于 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

Answer 3

这是一个在新行中打印从 1 到 n 的斐波那契数列成员的代码。需要注意的是，它使用了两个非常简单的辅助函数。希望这可以帮助。

;Prints to the screen all the member up to the nth member in the fibonaci sequence (define (fibo n)
 (let ((i 1))
  (if (= n 1)
      (display 1)
      (fiboHelp i n))))

;Helper function that presents Fibonaci sequence from bottom index i until upper index n
(define (fiboHelp i n)
  (if (= i n)
      (display(fiboMember i))
      (begin
        (display (fiboMember i))
        (newline)
        (fiboHelp (+ i 1)n)))) 

;Returns the nth member of the Fibonaci sequence
(define (fiboMember n)
  (if (<= n 2)
      (+ 1 0)
      (+ (fiboMember(- n 1))(fiboMember(- n 2)))))