请求解析双递归的原理及执行顺序

没问题！既然你已经搞懂单递归了，那双递归其实就是在同一个递归函数里，调用了两次自身——听起来好像只是多了一次调用，但执行顺序会变得有意思很多，咱们一步步拆开来捋清楚。

先看一个简单的双递归示例 #

咱们先拿一段直观的代码来分析，这样更容易跟上执行流程：

def double_recursion(n):
    if n <= 0:
        print("Base case reached!")
        return
    print(f"准备第一次调用 double_recursion({n-1})")
    double_recursion(n-1)
    print(f"准备第二次调用 double_recursion({n-2})")
    double_recursion(n-2)

用n=3拆解执行顺序 #

单递归是一条线走到底，直到触达base case再往回返；双递归则是先把第一条递归分支完全走完，再回头走第二条分支，相当于每个调用节点都分叉出两个子分支，像遍历一棵二叉树一样。咱们一步步看double_recursion(3)的执行过程：

1. 初始调用double_recursion(3)：n>0，打印「准备第一次调用 double_recursion(2)」，进入第一次递归调用double_recursion(2)
2. 进入double_recursion(2)：n>0，打印「准备第一次调用 double_recursion(1)」，进入double_recursion(1)
3. 进入double_recursion(1)：n>0，打印「准备第一次调用 double_recursion(0)」，进入double_recursion(0)
4. 进入double_recursion(0)：触发base case，打印「Base case reached!」，返回上一层（回到double_recursion(1)）
5. 回到double_recursion(1)：第一次递归执行完，打印「准备第二次调用 double_recursion(-1)」，进入double_recursion(-1)
6. 进入double_recursion(-1)：触发base case，打印「Base case reached!」，返回上一层（回到double_recursion(1)），此时double_recursion(1)执行完毕，返回上一层（回到double_recursion(2)）
7. 回到double_recursion(2)：第一次递归执行完，打印「准备第二次调用 double_recursion(0)」，进入double_recursion(0)
8. 进入double_recursion(0)：触发base case，打印「Base case reached!」，返回上一层（回到double_recursion(2)），此时double_recursion(2)执行完毕，返回上一层（回到double_recursion(3)）
9. 回到double_recursion(3)：第一次递归执行完，打印「准备第二次调用 double_recursion(1)」，进入double_recursion(1)
10. 这个新的double_recursion(1)会重复步骤3-6的流程：走完第一次调用分支，再走第二次调用分支，最后返回double_recursion(3)
11. 最终double_recursion(3)执行完毕，整个流程结束

核心规律总结 #

双递归的执行本质是深度优先遍历：

• 每遇到一次递归调用，就先钻进去把这个分支的所有子调用都执行完，直到触达base case才往回走
• 等第一条分支完全走完返回后，才会开始执行第二条递归分支
• 所有的递归调用会形成一棵「调用树」，我们先遍历左子树的所有节点，再遍历右子树的所有节点

再举个常见的双递归场景：斐波那契递归实现 #

你肯定见过这个经典例子，它就是典型的双递归：

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

当调用fib(5)时，程序会先递归计算fib(4)（直到拆成fib(1)和fib(0)得到结果），等fib(4)的结果返回后，才会开始计算fib(3)，再把两个结果相加得到最终值。不过要注意，这种实现会重复计算大量子问题（比如fib(3)会被fib(4)和fib(5)各调用一次），所以实际中常用动态规划来优化。

内容的提问来源于stack exchange，提问作者Oleg Radchenko