博客

什么是递归？

递归是一种重要的算法思想，它将问题拆解成规模更小的子问题，并通过调用自身来解决这些子问题，最终达到解决原始问题的目的。因此，递归非常适合于解决能够自我拆解的问题，例如树形结构、图的遍历等。

递归算法的特点

递归算法的特点主要有以下几点：

1. 递归函数会重复调用自身，直到满足某个条件才会停止递归。
2. 每次递归调用都会产生一个新的局部变量空间，函数参数和局部变量都有自己独立的内存地址。
3. 递归的算法时间复杂度可能较高，因为每次递归都需要新建一些变量和内存空间。

递归算法的应用场景

递归算法常用于多叉树和二叉树的遍历、图的遍历和搜索、字符串和数组的排列等问题。例如，在树形结构中，我们可以使用递归算法来遍历整个树形结构，实现对每个节点的访问和操作。

下面，我们来看一下递归算法的两个具体的应用场景：

递归算法应用场景1：求 N 的阶乘

阶乘指从1到N的所有自然数相乘的积，因为阶乘的自我拆解性质，因此可以使用递归来实现求解。

def factorial(n):
    """
    计算 n 的阶乘
    """
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

在上面的代码中，我们首先判断 n 是否等于1，如果等于1则直接返回 1，否则就继续递归调用 factorial(n-1)，直到 n 等于1才会停止递归。

递归算法应用场景2：二叉树遍历

二叉树遍历是递归算法的经典应用，二叉树有前序遍历、中序遍历和后序遍历三种方式，下面我们来看一下如何使用递归算法实现前序遍历。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorderTraversal(root):
    """
    二叉树前序遍历
    """
    if not root:
        return []
    res = [root.val]
    res += preorderTraversal(root.left)
    res += preorderTraversal(root.right)
    return res

在上面的代码中，首先判断根节点是否为 None，如果为 None 则直接返回空列表，否则将根节点的值加入到结果列表中，然后递归调用左子树和右子树，最后将左子树和右子树的遍历结果添加到 res 列表中并返回。

总结

递归算法是一种十分重要的算法思想，它能够有效地解决很多复杂的问题。在使用递归算法时，要注意把握好递归的终止条件和递归调用的变量，避免出现死循环和栈溢出的问题。