（递归）算法

递归条件：

1.终止条件，当满足这个条件时，递归将停止并返回一个值，这个条件是为了防止函数无限递归，导致栈溢出。

2.递归条件，这个是函数调用自身的地方，通常是通过将问题分解为更小的子问题来解决。

例如求n的阶乘：

def factorial(n):
    # 基线条件
    if n == 0:
        return 1
    # 递归条件
    else:
        return n * factorial(n - 1)

当我们做题时，面对递归问题，应当分析递归，这时需用到递归树

原式中为2T(n/2),所以分为俩节点

计算树每层的复杂度，将所有层的复杂度相加得到最终的复杂度。

适合使用递归的题目类型

1. 自然递归结构的问题：

   • 分治法：可以将问题分解为多个相同或相似的子问题，例如归并排序、快速排序。
   • 树和图的遍历：如二叉树的前序、中序、后序遍历，图的深度优先搜索（DFS）。
   • 排列组合：生成排列、组合、子集等问题。

2. 递归定义清晰的问题：

   • 数学递归问题：如阶乘计算、斐波那契数列。
   • 字符串处理：如回文检测、字符串匹配。

3. 递归生成特性的问题：

   • 分形图形：如Sierpinski三角形、Koch雪花。
   • 动态规划：某些动态规划问题可以通过递归+记忆化的方式解决。

不适合使用递归的题目类型

1. 性能敏感问题：

   • 深度递归：递归深度较大的情况下，可能会导致栈溢出问题。
   • 重复计算：如斐波那契数列的纯递归实现会多次计算相同的子问题，效率较低。对于这种情况，可以使用动态规划或记忆化递归来优化。

2. 迭代更适合的问题：

   • 线性遍历：如数组的遍历、链表操作。
   • 循环结构清晰的问题：如查找、排序（除了归并和快速排序）。

3. 状态管理复杂的问题：

   • 状态机：某些需要维护复杂状态的问题，迭代方法可能更易于实现和管理。