3. 递归函数

什么是递归函数

递归函数是指在函数内部直接或间接调用自身的函数。

递归函数通过将问题分解为更小的同类子问题来解决问题，直到达到一个终止条件，从而避免循环和当前数据压栈、弹栈等操作。

作用

简化特殊场合的编程难度，如：遍历二叉树、快速排序等场景。

递归示意

阶乘：n! = 1 * 2 * 3 * ... * n

求5!

5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1

递归求阶乘

def factorial(n):
    '使用递归计算阶乘!'
    if n == 1:
        return 1
    result = n * factorial(n - 1)
    return result

print("3! = ", factorial(3))

递归函数-原理

• 当一个函数A调用另外一个函数B时，A正在运行的环境（局部变量）会保存在栈空间中，直到B函数返回为止。
• 当一个函数A调用另外一个函数A时（自己时）也是如此。

递归的优缺点

优点

• 代码简洁：适合解决分治问题（如快速排序、树的遍历等操作）。
• 更符合数学定义：如阶乘、斐波那契数列的数学描述直接对应递归代码。

缺点

• 栈溢出风险：深层递归可能导致调用栈溢出（python默认调用深度1000层）。
• 性能问题：可能存在重复计算导致性能下降。