Python中 递归（Recursion）的使用浅析

递归的定义

递归是一种在函数定义中调用函数自身的编程技巧和算法设计方法。

递归中有两个关键要素

1.  递归的终止条件。当满足这个条件时，递归不再继续调用自身，而是开始返回结果。这也叫 递归基例（Base Case）。 如果没有正确设置递归基例，递归函数将无限地调用自身，直到耗尽系统资源（如栈空间），导致程序崩溃。

2. 递归的调用（Recursive Call），也就是调用自身函数

递归的使用场景

对于逐级迫进求解的情形，比如阶乘，树的深度等的程序设计情形，是使用递归的场景。类似功能的实现，在Python里面有迭代器和生成器（以类或函数为基础的单值生成器）。

对于简单的迭代，比如阶乘、斐波那契数列，用递归函数可以，但是不如迭代器、生成器高效，因为它们的本质是执行一次后停下再按要求执行下一次，而递归调用的本质是不断压栈，会占用大量的栈空间，如果递归深度过大（例如处理大规模数据或者复杂的递归结构时），可能会导致栈溢出错误。

但是对于树，似乎递归是合适的解法之一（DFS)。

所以要清楚递归的缺点 （from “豆包”）： 

• 递归调用会占用大量的栈空间，如果递归深度过大（例如处理大规模数据或者复杂的递归结构时），可能会导致栈溢出错误。

举例说明：

1. 阶乘 （个人认为，Python 中不推荐用递归来做这种实现，因为递归函数的缺点）

def factorial(n):
    if n == 0:   #中止条件
        return 1 
    result = n * factorial(n - 1)  #调用自身
    return result

2. 倒数

def countdown(n):
    print(n)
    if n <= 0:  # 这是一个不调用自身的分支，是终止条件
        return
    countdown(n - 1)

 3. 判断二叉树的深度 （Leetcode 104 题）

LeetCode  -- 104. 二叉树的最大深度https://leetcode.cn/problems/maximum-depth-of-binary-tree/

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # 深度优先搜索
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:   #终止条件
            return 0
        l = self.maxDepth(root.left)    #对左分支调用自身
        r = self.maxDepth(root.right)   #对右分支调用自身
        return 1 + max(l, r)

4. 反转二叉树（LeetCode 226题）

LeetCode --  226. 翻转二叉树https://leetcode.cn/problems/invert-binary-tree/

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # 我的解法，用递归
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None:
            return root
        root.left, root.right = root.right, root.left
        self.invertTree (root.left)
        self.invertTree(root.right)
        return root