树形递归

介绍树形递归模式，通过爬楼梯和换零钱两个例子展示多次递归调用的用法与代价。

一类新问题

有一类问题，我们还没有明确描述过它们的递归模式。看看下面这个问题：

我想上一段有 n 级台阶的楼梯。我每次可以上 1 级或 2 级。有多少种不同的上楼方式？

例如，当 n 为 5 时，有 8 种可能的方式：

为了解决这个问题，我们要引入一种称为树形递归（tree recursion）的模式。树形递归只是个说法，用来描述你在递归情况中发起不止一次递归调用的情形。为什么这里需要这样做？看看上面问题的一个解法：

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

把这个过程拆解开，有三部分需要考虑：

有两个基本情况，对应两种不同结果。
- 如果只有一级台阶要爬，那就只有一种走法（爬上那一级）。
- 如果有两级台阶要爬，那正好有两种走法（先 1 级再 1 级，或者直接 2 级）。
否则，问题被拆成两个「世界」来缩小规模。
- 在第一个世界中，我们上一级台阶，于是剩余台阶数减 1。
- 在第二个世界中，我们上两级台阶，于是剩余台阶数减 2。
对这两个更小的子问题分别发起递归调用，就得到了子问题的答案；把它们加起来，就得到了原问题的答案。

count-stairs 是树递归的，因为每当它被调用，递归调用就会分支展开，形成一棵倒置的树。例如 (count-stairs 5)：

换零钱问题

再看一个更难的问题：

给定半美元、25 美分、10 美分、5 美分和 1 美分，把 1 美元换成零钱有多少种不同方式？更一般地，我们能不能写一个函数，计算用任意一组面额把任意给定金额换成零钱的方式数？

我们用与上面类似的方式来处理这个问题。仔细琢磨问题描述，我们会发现需要跟踪两样东西：当前的金额，以及我们可用的硬币（可以用一个句子来跟踪，例如 '(50 25 10 5 1)）。由此，我们可以观察到几个关于基本情况的要点：

如果金额恰好是 0，我们应将其计为 1 种换零钱方式。
- 这看起来可能有违直觉，但把 0 美元换成零钱恰好有一种方式——一枚硬币都不用。
如果金额小于 0，我们应将其计为 0 种方式。
- 你不可能把负数金额换成零钱！
如果我们用完了可用的硬币，我们应将其计为 0 种方式。
- 等我们考虑了递归情况，这一点会更直观。

对于递归情况，我们同样要发起两次递归调用。这两次递归调用把问题分成两个世界：

在其中一个世界里，我们使用最大的硬币（(50 25 10 5 1) 的 first）。
- 硬币为什么按这个顺序排列？因为这样容易推理。句子也可以按不同顺序排列，虽然会影响计算过程，但不会影响结果。
在另一个世界里，我们再也不使用最大的硬币。
- 例如，如果我们再也不使用半美元，新的句子就是 (25 10 5 1)。

把这些翻译成代码，我们得到：

(define (count-change amount)
  (cc amount `(50 25 10 5 1)))

(define (cc amount kinds-of-coins)
  (cond [(= amount 0) 1]
        [(or (< amount 0) (empty? kinds-of-coins)) 0]
        [else (+ (cc amount
                     (bf kinds-of-coins))
                 (cc (- amount
                        (first kinds-of-coins))
                     kinds-of-coins))] ))

关于时间效率

树递归过程通常需要指数时间来计算。那我们为什么还要用它们呢？

有些问题用树形递归的思路更容易解决。试试用其他语言的 for 循环来写 count-change 看看。
有些问题难到难以处理（intractably hard），意味着我们已知最快的算法仍然是指数级运行时间。
事实证明，我们可以在不改变其形状的前提下优化树递归过程，这一点我们将在课程后面介绍。

树形递归

一类新问题

换零钱问题

关于时间效率

延伸阅读