UC Berkeley CS61A Sping 2021 Lecture 7 Tree Recursion

树形递归

树形递归（Tree Recursion） 是指递归调用不仅仅是调用自身一次，而是调用自己多个次数，从而形成一个类似树状的结构。在树形递归中，每个递归调用可以生成多个子问题，这些子问题进一步递归调用自己，最终产生一个树状的递归调用结构。

树形递归的特点：

1. 多个子问题：每个递归调用不仅会调用一次自身，还可能会产生多个递归调用，形成“树”的分支。
2. 递归深度增加：每次递归调用都可能生成多个子递归调用，因此递归的深度比线性递归要大。

例子：斐波那契数列（Fibonacci Sequence）

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

• 解释：

  • 对于 fibonacci(5)，它将计算 fibonacci(4) 和 fibonacci(3)，然后再分别计算这两个值。
  • 每次 fibonacci 函数调用会继续调用两个子问题（fibonacci(n-1) 和 fibonacci(n-2)），从而形成一棵递归调用的“树”。

  递归树如下：
  fibonacci(5)
  /
  fibonacci(4) fibonacci(3)
  / \ /
  fibonacci(3) fibonacci(2) fibonacci(2) fibonacci(1)
  / \ / \ /
  fibonacci(2) fibonacci(1) fibonacci(1) fibonacci(0)

树形递归的计算成本：

• 在树形递归中，许多子问题会被重复计算。以斐波那契数列为例，fibonacci(3) 被调用了两次，而 fibonacci(2) 被调用了三次。这样会导致冗余的计算。
• 可以通过记忆化（memoization）或动态规划（dynamic programming）来优化树形递归，避免重复计算。

其他树形递归的例子：

1. 汉诺塔问题（Tower of Hanoi）：

   • 每次递归调用都会把问题分成多个子问题，因此可以看作是树形递归。

2. 排列与组合（Permutations and Combinations）：

   • 求排列或组合问题时，递归会分别计算多个选择，从而形成树状结构。

总结：

树形递归的特征是每个递归调用都会生成多个子问题，这些子问题会再次递归调用，最终形成一个递归树结构。它可以用来解决许多复杂的问题，但也可能带来重复计算的问题，需要优化以提高效率。

一个问题，和上面的tree recurtion好像没啥联系

然后利用FUNC是non-decreasing（单调不减）的特点，怎么能让这个速度快一点？
下面这个方法还是一个尾递归，因为即便有两个调用，但是只执行了其中一个

这个问题是一个找路的问题，是tree recurtion的一个例子，比较繁琐

这道题是一个经典的 路径计数问题，具体目标是计算从某个起始位置到达目标位置的不被阻挡的路径数。题目给定了一个 网格，并且网格中的某些格子被阻挡，不能通过。我们需要递归地计算所有可能的路径，并返回能够到达目标位置的路径数量。

题目目标：

• 输入：

  • 一个 网格，其中某些格子被阻挡，表示为 blocked(x, y)，如果位置 (x, y) 被阻挡或者超出网格边界，返回 True，否则返回 False。
  • 起始位置 (x0, y0)，表示路径开始的位置。
  • 目标位置是 (x1, 0)，即目标始终在第一行。

• 输出：

  • 从 (x0, y0) 到达 (x1, 0) 的所有不被阻挡的路径的数量。

解题思路：

1. 递归：

   • 使用递归来探索从当前位置 (x0, y0) 到目标 (x1, 0) 的所有路径。
   • 对于每个位置 (x0, y0)，有三个可能的方向可以尝试：向左上（(x0-1, y0-1)），向上（(x0, y0-1)），向右上（(x0+1, y0-1)）。
   • 每次递归都尝试这些方向，直到找到目标位置或者到达被阻挡的格子。

2. 递归基准条件：

   • 如果当前位置 (x0, y0) 被阻挡，返回 0，表示无法通过此位置。
   • 如果 y0 == 0（到达目标行），返回 1，表示找到一条有效路径。
   • 否则，继续递归尝试三个方向。

3. 路径计数：

   • 对于每个位置 (x0, y0)，递归地计算从该位置出发的所有路径，将其结果加总。

递归实现：

def num_paths(blocked, x0, y0):
    """返回从 (x0, y0) 到达 (x1, 0) 的路径数量，不能通过被阻挡的格子。"""
    
    if blocked(x0, y0):  # 如果当前位置被阻挡，返回 0
        return 0
    elif y0 == 0:  # 如果到达目标行，返回 1
        return 1
    else:  # 否则递归地检查三个可能的方向
        return (num_paths(blocked, x0-1, y0-1) +  # 向左上
                num_paths(blocked, x0, y0-1) +    # 向上
                num_paths(blocked, x0+1, y0-1))   # 向右上

解释：

1. blocked(x0, y0)：判断当前位置 (x0, y0) 是否被阻挡，如果被阻挡则返回 0，表示不能经过此位置。
2. 基准条件：
   • y0 == 0：如果 y0 等于 0，表示我们已经到达目标行，返回 1，表示找到一条路径。
   • blocked(x0, y0)：如果当前位置被阻挡，则不能继续前进，返回 0。
3. 递归调用：
   • 对于当前位置 (x0, y0)，我们递归地检查三个方向的路径：
     • 向左上方：num_paths(blocked, x0-1, y0-1)
     • 向上：num_paths(blocked, x0, y0-1)
     • 向右上方：num_paths(blocked, x0+1, y0-1)
   • 将这三个递归结果相加，表示从当前位置可以到达目标位置的所有路径数。

例子：

假设给定的网格如下，其中被阻挡的位置用黑色圆点表示：

0 1 2 3 4 5 6 7 8 9
-------------------
0 |   ● ● ● ● ● ● |
1 |   ●           |
2 |     ●         |
3 |   ●     ●     |
4 |   ●           |
5 | ●             |
6 |   ● ● ● ● ● ● |

例1：

• 假设我们从 (5, 6) 开始，目标是到达 y0 == 0（第一行）。
• num_paths(M, 5, 6) 返回 1，表示存在 1 条路径。

例2：

• 给定一个不同的网格 M2，num_paths(M2, 5, 6) 返回 5，表示存在 5 条不被阻挡的路径。

总结：

• 这个问题通过递归方法，逐步计算从起始点到目标点的所有不被阻挡的路径。
• 递归的核心在于探索当前点的三个可能方向，并累加这些方向上的路径数。

下一个tree recurtion问题，如何找出一个数用整数拆分的各种可能（现在拆分的数的大小）

比如这个拆分6里面限制最大数是3

解法如下，注意看他是怎么思考的

根据上面这里的思路，他写出来的代码是这样的