看不懂这个树递归问题

Question

所以我正在阅读 SICP 书。我在树递归一章。我用谷歌搜索树递归以获得更多关于它的知识，我偶然发现了这个练习，我很难完全理解它。

练习：

I want to go up a flight of stairs that has n steps. I can either take 1 or 2 steps each time. How many different ways can I go up this flight of stairs?

答案是：

比如nis 5的情况下，有8种可能的方式：

1 1 1 1 1

2 1 1 1

1 2 1 1

1 1 2 1

1 1 1 2

1 2 2

2 1 2

2 2 1

这是我无法完全理解的代码块：

(define (count-stairs n)
  (cond [(= n 1) 1]
        [(= n 2) 2]
        [else (+ (count-stairs (- n 1))
                 (count-stairs (- n 2)) ]) ))

说明过程的图片

我的问题是，为什么会有 + 号？ count-stairs(4) + count-stairs(3) 不是 7 步吗？或者我在这里遗漏了一些东西

此外：这是完整的 link 练习 https://berkeley-cs61as.github.io/textbook/tree-recursion.html

需要你的帮助！

Answer 1

树状图仅给出 space 的函数调用及其以 (count-stairs 5) 开头的参数。当我们调用带有参数 5 的函数时，它会根据表达式 (count-stairs (- n 1)) 调用 (count-stairs 4)，并且由于表达式 (count-stairs (- n 2)) 而调用 (count-stairs 3)。当然，这些值与 + 相加，成为调用的 return 值。树只是不显示 return 值信息，只显示调用参数。

(count-stairs 5) 并不意味着 "count five stairs"，而是 "call the count-stairs function with argument 5 to calculate how many different ways there are to go up a flight of 5 stairs"。

对于 (count-stairs 3)，结果将为 3，因为 (count-stairs 1) 和 (count-stairs 2) 分别只是 return 1 和 2。

但是，(count-stairs 4) 添加了 (count-stairs 3) 和 (count-stairs 2)，因此 (count-stairs 4) -> 5。

我们可以使用这种箭头表示法用它们的结果值来注释树中的表达式，从底部开始向上工作。在树的顶部，我们将以 (count-stairs 5) -> 8.

结束

count-stairs 只是伪装的递归斐波那契函数的微小变化。

为什么要计算使用 1 级或 2 级台阶上楼梯的方式数？首先，基本情况明确。如果楼梯有一个台阶，那么只有一种方法可以穿过它：我们迈出那一步。所以(count-stairs 1) -> 1。如果有两步，那么就有两种方法：一步一步走，或者一步一步走。因此 (count-stairs 2) -> 2。然后是棘手的归纳部分。如果我们面临三个或更多楼梯，解决方案是什么？

如果我们面对一个有n级台阶的楼梯，n > 2，那么关于如何开始攀登我们有两种可能性。可能性（1）：我们可以先走一步，然后再爬剩下的n-1步楼梯；或者，可能性（2）我们可以将两步作为一步，然后爬上剩余的n-2步楼梯。这样n步的爬法数就是这两种可能的爬法数之和：n-1步的爬法数加上n-2步的爬法数

看不懂这个树递归问题

Can't understand this Tree recursion problem

lisp

recursion

binary-tree

sicp