递归

简介

递归（recursion）是一种算法策略，通过函数调用自身来解决问题。它主要包含两个阶段。

递：程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到“终止条件”。
归：触发“终止条件”后，程序从最深层的递归函数开始逐层返回，汇聚每一层的结果。

而从实现的角度看，递归代码主要包含三个要素。

终止条件：用于决定什么时候由“递”转“归”。
递归调用：对应“递”，函数调用自身，通常输入更小或更简化的参数。
返回结果：对应“归”，将当前递归层级的结果返回至上一层。

递归函数每次调用自身时，系统都会为新开启的函数分配内存，以存储局部变量、调用地址和其他信息等。这将导致两方面的结果。

函数的上下文数据都存储在称为“栈帧空间”的内存区域中，直至函数返回后才会被释放。因此，递归通常比迭代更加耗费内存空间。
递归调用函数会产生额外的开销。因此递归通常比循环的时间效率更低。

相较于迭代，递归的性能可能会较低，但是递归的代码会更加直观。

基本示例

def cumsum(num: int) -> int:
    """累加"""
    if num <= 0:
        return 0
    else:
        return num + cumsum(num - 1)


def multiply(num: int) -> int:
    """累乘"""
    if num <= 0:
        return 1
    else:
        return num * multiply(num - 1)


def fib(num: int) -> int:
    """斐波拉契数列"""
    if num == 1 or num == 2:
        return 1
    else:
        return fib(num - 1) + fib(num - 2)


if __name__ == "__main__":
    print(cumsum(15))  # 120
    print(multiply(15))  # 1307674368000
    print(fib(15))  # 610

尾递归

如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空间效率上与迭代相当。这种情况被称为尾递归（tail recursion）。

普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文。
尾递归：递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后，无须继续执行其他操作，因此系统无须保存上一层函数的上下文。

简介​

基本示例​

尾递归​

简介

基本示例

尾递归