如何理解递归

在二叉树的题目中，我们难免会用到递归方法，递归思想很简单，但运用起来却因为抽象而难以理解。

理解递归的关键在于认识到它是一种解决问题的方法，允许函数直接或间接地调用自身。以下是对递归的概述以及如何理解它的几个要点：

1. 基本概念

递归是用一个函数调用其自身来解决问题。每次递归调用都会处理问题的一部分，直到达到一个基本情况（即停止条件）。

2. 结构

通常，递归包含两部分：

• 基本情况（Base Case）：这是停止递归的条件。没有这个条件，递归将无限进行，导致栈溢出。
• 递归情况（Recursive Case）：这是函数调用自身以解决更小的子问题。

3. 示例：阶乘

一个经典的递归示例是计算阶乘。定义阶乘的递归形式如下：

• ( n! = n \times (n-1)! )（递归情况）
• ( 0! = 1 )（基本情况）

其实现如下：

def factorial(n: int) -> int:if n == 0:  # 基本情况return 1else:  # 递归情况return n * factorial(n - 1)

在调用 factorial(5) 时，实际的调用过程是这样的：

• factorial(5) 计算 5 * factorial(4)
• factorial(4) 计算 4 * factorial(3)
• factorial(3) 计算 3 * factorial(2)
• factorial(2) 计算 2 * factorial(1)
• factorial(1) 计算 1 * factorial(0)
• factorial(0) 返回 1

4. 可视化递归

为了帮助理解递归，可以使用树结构来可视化。例如，当计算 factorial(5) 时，可以画出一棵树，显示每个函数调用如何分支到下一个调用。最终，每个分支都返回结果，汇总至最顶层的函数。

5. 递归的问题解决步骤

获取递归解法的一般步骤：

1. 定义问题：了解要解决的具体问题。
2. 找出基本情况：明确何时停止递归。
3. 确定递归关系：如何将大问题拆分为更小的子问题。
4. 通过示例理解执行过程：逐步追踪函数调用，以深入理解每一步的作用。

6. 递归 vs 迭代

• 递归方法可以有更简洁和更具可读性的实现，但有时更容易导致性能问题（例如过多的函数调用可能导致栈溢出）。
• 循环（或迭代）通常会更高效，尤其是在不需要存储调用栈的情况下。

7. 实践

解决各种问题（如遍历树、斐波那契数列、背包问题等）可以加强对递归的理解。实践是掌握递归最有效的方式。

我们来看看力扣144题目：二叉树的前序遍历


代码不好理解的话，可以在自己的电脑上运行下面的代码。

from typing import Optional, List  # 定义二叉树节点类  
class TreeNode:  def __init__(self, val=0, left=None, right=None):  self.val = val  self.left = left  self.right = right  # 定义Solution类并实现前序遍历方法  
class Solution:  def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:  # 打印当前节点的值  if not root:  print("当前节点: None")  return []  print(f"当前节点: {root.val}")  result = []  result.append(root.val)  # 添加根节点的值  print(f"当前结果: {result}")  # 打印结果  # 递归遍历左子树  left_result = self.preorderTraversal(root.left)  result.extend(left_result)  # 递归遍历右子树  right_result = self.preorderTraversal(root.right)  result.extend(right_result)  print(f"返回结果: {result}")  # 打印返回的结果  return result  # 示例：创建一棵二叉树并运行前序遍历  
if __name__ == "__main__":  # 创建二叉树  #      1  #     / \#    2   3  #   / \#  4   5  root = TreeNode(1)  root.left = TreeNode(2)  root.right = TreeNode(3)  root.left.left = TreeNode(4)  root.left.right = TreeNode(5)  # 创建解决方案实例并调用前序遍历  solution = Solution()  result = solution.preorderTraversal(root)  # 输出最终结果  print(f"最终前序遍历结果: {result}")  # 输出应为 [1, 2, 4, 5, 3]

下面是图解递归算法：

前序遍历的顺序是：中左右。我们如何利用递归方法解决此道题目呢？我们可以假设一个简单的情况（root）不为空。

前序遍历，我们先把中值root.val添加到result中。接下来我们要处理左节点了，左节点也是要中左右，这个时候我们可以借助递归来处理这种重复的动作。

我们以下面的二叉树为例：

递归算法里其实就是在做三件事：