递归栈调用执行机制解析：以有序数组转平衡二叉搜索树代码为例

我当初第一次啃这个递归的时候，也卡在递归栈的细节上——阶乘那种线性递归还好理解，这种二叉树的分支递归确实容易绕晕。咱们就拿你的示例数组[-10,-3,0,5,9]一步步拆解，把递归栈的入栈、出栈和返回过程扒得明明白白～

先提个小细节：你的代码里mid = (len(arr)) / 2在Python3里会得到浮点数，直接用arr[mid]会报错，应该改成整数除法mid = len(arr) // 2，下面的演示我会用这个修正后的写法，不然没法正常执行哦。

递归栈的基本规则先明确 #

每次调用sortedArrayToBST时，程序会把当前函数的上下文（包括当前的arr、已经计算的mid、已经创建的root节点，还有执行到哪一行的位置）压入递归栈。只有当碰到base case（arr为空，返回None）时，才会开始从栈顶弹出函数调用，把结果返回给上一层调用者，继续执行上一层没完成的代码。

一步步走栈的变化（栈顶在右侧） #

我们用[调用X]表示栈的状态，每次新调用压入右侧，弹出也从右侧取。

1. 初始调用：sortedArrayToBST([-10,-3,0,5,9])（记为调用A）

• 栈状态：[调用A]
• 执行流程：
  • arr不为空，计算mid = 5//2 = 2，创建root = Node(0)
  • 接下来要执行root.left = sortedArrayToBST(arr[:2])，也就是调用sortedArrayToBST([-10,-3])（记为调用B），压入栈。

2. 调用B：sortedArrayToBST([-10,-3])

• 栈状态：[调用A, 调用B]
• 执行流程：
  • arr不为空，mid = 2//2 =1，创建root = Node(-3)
  • 执行root.left = sortedArrayToBST(arr[:1])，调用sortedArrayToBST([-10])（记为调用C），压入栈。

3. 调用C：sortedArrayToBST([-10])

• 栈状态：[调用A, 调用B, 调用C]
• 执行流程：
  • arr不为空，mid=1//2=0，创建root=Node(-10)
  • 执行root.left = sortedArrayToBST(arr[:0])（空数组，记为调用D），压入栈。

4. 调用D：sortedArrayToBST([])

• 栈状态：[调用A, 调用B, 调用C, 调用D]
• 执行流程：
  • 触发base case，返回None
  • 调用D完成，从栈弹出，栈变为[调用A, 调用B, 调用C]
  • 把None赋值给调用C的root.left，也就是Node(-10).left = None

5. 回到调用C，继续执行

• 栈状态：[调用A, 调用B, 调用C]
• 执行root.right = sortedArrayToBST(arr[0+1:])（空数组，记为调用E），压入栈。

6. 调用E：sortedArrayToBST([])

• 栈状态：[调用A, 调用B, 调用C, 调用E]
• 返回None，弹出栈，栈变为[调用A, 调用B, 调用C]
• 赋值给调用C的root.right，即Node(-10).right = None
• 调用C完成，返回Node(-10)，弹出栈，栈变为[调用A, 调用B]
• 把返回的Node(-10)赋值给调用B的root.left，即Node(-3).left = Node(-10)

7. 回到调用B，继续执行

• 栈状态：[调用A, 调用B]
• 执行root.right = sortedArrayToBST(arr[1+1:])（空数组，记为调用F），压入栈。

8. 调用F：sortedArrayToBST([])

• 返回None，弹出栈，栈变为[调用A, 调用B]
• 赋值给调用B的root.right，即Node(-3).right = None
• 调用B完成，返回Node(-3)，弹出栈，栈变为[调用A]
• 赋值给调用A的root.left，即Node(0).left = Node(-3)

9. 回到调用A，处理右子树

• 栈状态：[调用A]
• 执行root.right = sortedArrayToBST(arr[2+1:])（即[5,9]，记为调用G），压入栈。

10. 调用G：sortedArrayToBST([5,9])

• 栈状态：[调用A, 调用G]
• 执行流程：
  • mid=2//2=1，创建root=Node(9)
  • 执行root.left = sortedArrayToBST(arr[:1])（即[5]，记为调用H），压入栈。

11. 调用H：sortedArrayToBST([5])

• 栈状态：[调用A, 调用G, 调用H]
• 执行流程：
  • mid=1//2=0，创建root=Node(5)
  • 执行root.left = sortedArrayToBST(arr[:0])（空数组，记为调用I），压入栈。

12. 调用I：sortedArrayToBST([])

• 返回None，弹出栈，栈变为[调用A, 调用G, 调用H]
• 赋值给调用H的root.left，即Node(5).left = None

13. 回到调用H，继续执行

• 执行root.right = sortedArrayToBST(arr[0+1:])（空数组，记为调用J），压入栈。

14. 调用J：sortedArrayToBST([])

• 返回None，弹出栈，栈变为[调用A, 调用G, 调用H]
• 赋值给调用H的root.right，即Node(5).right = None
• 调用H完成，返回Node(5)，弹出栈，栈变为[调用A, 调用G]
• 赋值给调用G的root.left，即Node(9).left = Node(5)

15. 回到调用G，继续执行

• 执行root.right = sortedArrayToBST(arr[1+1:])（空数组，记为调用K），压入栈。

16. 调用K：sortedArrayToBST([])

• 返回None，弹出栈，栈变为[调用A, 调用G]
• 赋值给调用G的root.right，即Node(9).right = None
• 调用G完成，返回Node(9)，弹出栈，栈变为[调用A]
• 赋值给调用A的root.right，即Node(0).right = Node(9)

17. 最终：调用A完成

• 栈状态：[]（空栈）
• 调用A返回Node(0)，也就是整个平衡BST的根节点，流程结束。

关键总结 #

• 递归栈就像一个“待办清单”，每碰到新的递归调用就把当前任务暂停、压栈，先处理子任务
• 只有当子任务碰到base case（空数组）时，才会开始“清账”：弹出栈顶任务，把结果返回给上一级，完成上一级未完成的赋值操作
• 二叉树的递归是先深度遍历左子树，再回溯处理右子树，整个栈的入栈出栈过程正好对应了这个深度优先的遍历顺序

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