介绍一下递归（Python + C++）

递归的概念递归是一种函数调用自身的编程技术通常用于解决可分解为相似子问题的问题。递归函数包含两个关键部分基线条件终止条件和递归条件调用自身的条件。Python 中的递归实现Python 递归示例计算阶乘def factorial(n): if n 1: # 基线条件 return 1 else: # 递归条件 return n * factorial(n - 1)Python 递归示例斐波那契数列def fibonacci(n): if n 1: # 基线条件 return n else: # 递归条件 return fibonacci(n - 1) fibonacci(n - 2)C 中的递归实现C 递归示例计算阶乘int factorial(int n) { if (n 1) { // 基线条件 return 1; } else { // 递归条件 return n * factorial(n - 1); } }C 递归示例斐波那契数列int fibonacci(int n) { if (n 1) { // 基线条件 return n; } else { // 递归条件 return fibonacci(n - 1) fibonacci(n - 2); } }递归的优缺点优点代码简洁逻辑清晰适合解决分治类问题如树遍历、汉诺塔。数学表达式直接映射为代码如阶乘、斐波那契数列。缺点可能引发栈溢出如未正确设置基线条件。重复计算问题如斐波那契数列的朴素递归效率低。优化递归的方法尾递归优化以阶乘为例def factorial_tail(n, acc1): if n 1: return acc return factorial_tail(n - 1, acc * n)记忆化缓存中间结果from functools import lru_cache lru_cache def fibonacci_memo(n): if n 1: return n return fibonacci_memo(n - 1) fibonacci_memo(n - 2)