Recursion

递归是一种编程和数学中的技术，其中一个函数直接或间接地调用自身以解决问题。递归通常用于将一个复杂的问题分解为更简单的子问题，直到达到一个基本情况（基准情况），这个基本情况可以直接解决。

递归有两个基本的组成部分：

1. 基准情况：这是递归的终止条件，指明何时停止递归调用。没有基准情况，递归将无限进行下去，导致栈溢出错误。

2. 递归步骤：这是函数调用自身的部分，通常会将问题规模缩小，逐步接近基准情况。

递归的思想同动态规划的思想有一致性，如果回忆大学的算法课程，动态规划的起点一般是从讨论某一个递归算法的重复计算问题开始的。两者的实际差别在具体的算法代码实现上，递归的代码基本就是递归的基准情况和步骤的自然组合；动态规划在拆分问题时可以使用递归的思想，但在实现时，却是从小到大，和从大大小拆分的思想相反。

以下是一个计算阶乘的递归示例：

def factorial(n):
    # 基准情况
    if n == 0 or n == 1:
        return 1
    # 递归步骤
    else:
        return n * factorial(n - 1)
 
# 使用示例
print(factorial(5))  # 输出 120

递归的优点：

• 代码简洁：递归可以使代码更简洁和易于理解，特别是在处理树形结构或分治算法时。
• 自然表达：某些问题（如树遍历、图遍历等）用递归表达更自然。

递归的缺点：

• 性能：递归可能导致较高的时间复杂度，尤其是在没有优化的情况下（如重复计算）。但这点并不是绝对的，还是应该以实际的性能测试为准。
• 空间消耗：每次递归调用都会在调用栈上占用空间，深度递归可能导致栈溢出。