在二叉樹的題目中，我們難免會用到遞歸方法，遞歸思想很簡單，但運用起來卻因為抽象而難以理解。

理解遞歸的關(guān)鍵在于認識到它是一種解決問題的方法，允許函數(shù)直接或間接地調(diào)用自身。以下是對遞歸的概述以及如何理解它的幾個要點：

1. 基本概念

遞歸是用一個函數(shù)調(diào)用其自身來解決問題。每次遞歸調(diào)用都會處理問題的一部分，直到達到一個基本情況（即停止條件）。

2. 結(jié)構(gòu)

通常，遞歸包含兩部分：

• 基本情況（Base Case）：這是停止遞歸的條件。沒有這個條件，遞歸將無限進行，導(dǎo)致棧溢出。
• 遞歸情況（Recursive Case）：這是函數(shù)調(diào)用自身以解決更小的子問題。

3. 示例：階乘

一個經(jīng)典的遞歸示例是計算階乘。定義階乘的遞歸形式如下：

• ( n! = n \times (n-1)! )（遞歸情況）
• ( 0! = 1 )（基本情況）

其實現(xiàn)如下：

def factorial(n: int) -> int:if n == 0:  # 基本情況return 1else:  # 遞歸情況return n * factorial(n - 1)

在調(diào)用 factorial(5) 時，實際的調(diào)用過程是這樣的：

• 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. 可視化遞歸

為了幫助理解遞歸，可以使用樹結(jié)構(gòu)來可視化。例如，當計算 factorial(5) 時，可以畫出一棵樹，顯示每個函數(shù)調(diào)用如何分支到下一個調(diào)用。最終，每個分支都返回結(jié)果，匯總至最頂層的函數(shù)。

5. 遞歸的問題解決步驟

獲取遞歸解法的一般步驟：

1. 定義問題：了解要解決的具體問題。
2. 找出基本情況：明確何時停止遞歸。
3. 確定遞歸關(guān)系：如何將大問題拆分為更小的子問題。
4. 通過示例理解執(zhí)行過程：逐步追蹤函數(shù)調(diào)用，以深入理解每一步的作用。

6. 遞歸 vs 迭代

• 遞歸方法可以有更簡潔和更具可讀性的實現(xiàn)，但有時更容易導(dǎo)致性能問題（例如過多的函數(shù)調(diào)用可能導(dǎo)致棧溢出）。
• 循環(huán)（或迭代）通常會更高效，尤其是在不需要存儲調(diào)用棧的情況下。

7. 實踐

解決各種問題（如遍歷樹、斐波那契數(shù)列、背包問題等）可以加強對遞歸的理解。實踐是掌握遞歸最有效的方式。

我們來看看力扣144題目：二叉樹的前序遍歷


代碼不好理解的話，可以在自己的電腦上運行下面的代碼。

from typing import Optional, List  # 定義二叉樹節(jié)點類  
class TreeNode:  def __init__(self, val=0, left=None, right=None):  self.val = val  self.left = left  self.right = right  # 定義Solution類并實現(xiàn)前序遍歷方法  
class Solution:  def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:  # 打印當前節(jié)點的值  if not root:  print("當前節(jié)點: None")  return []  print(f"當前節(jié)點: {root.val}")  result = []  result.append(root.val)  # 添加根節(jié)點的值  print(f"當前結(jié)果: {result}")  # 打印結(jié)果  # 遞歸遍歷左子樹  left_result = self.preorderTraversal(root.left)  result.extend(left_result)  # 遞歸遍歷右子樹  right_result = self.preorderTraversal(root.right)  result.extend(right_result)  print(f"返回結(jié)果: {result}")  # 打印返回的結(jié)果  return result  # 示例：創(chuàng)建一棵二叉樹并運行前序遍歷  
if __name__ == "__main__":  # 創(chuàng)建二叉樹  #      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)  # 創(chuàng)建解決方案實例并調(diào)用前序遍歷  solution = Solution()  result = solution.preorderTraversal(root)  # 輸出最終結(jié)果  print(f"最終前序遍歷結(jié)果: {result}")  # 輸出應(yīng)為 [1, 2, 4, 5, 3]

下面是圖解遞歸算法：

前序遍歷的順序是：中左右。我們?nèi)绾卫眠f歸方法解決此道題目呢？我們可以假設(shè)一個簡單的情況（root）不為空。

前序遍歷，我們先把中值root.val添加到result中。接下來我們要處理左節(jié)點了，左節(jié)點也是要中左右，這個時候我們可以借助遞歸來處理這種重復(fù)的動作。

我們以下面的二叉樹為例：

遞歸算法里其實就是在做三件事：