递归算法讲解(c基础)

1. 递归的定义
   • 递归是指在函数的定义中使用函数自身的方法。它是一种解决问题的策略，将一个大型复杂的问题逐步分解为规模更小的、与原问题相似的子问题来解决。当子问题的规模足够小，达到一个可以直接求解的基本情况（也称为终止条件）时，递归过程就停止。
2. 递归的组成部分
   • 递归调用：函数在其内部调用自身的操作。例如，计算阶乘的函数factorial(n)中，return n * factorial(n - 1)这一行就是递归调用。它表示为了计算n的阶乘，需要先计算n - 1的阶乘，以此类推。
   • 终止条件：这是递归的关键部分，用于停止递归调用，避免无限循环。以阶乘函数为例，当n == 0或n == 1时，factorial(n)直接返回1，这就是终止条件。因为0的阶乘和1的阶乘定义为1，此时不需要再进行递归调用。
3. 递归的执行过程（以阶乘函数为例）
   • 假设我们要计算5的阶乘，即factorial(5)。
   • 首先，进入factorial函数，因为n = 5不满足终止条件（n!=0且n!=1），所以执行return n * factorial(n - 1)，此时需要计算factorial(4)。
   • 对于factorial(4)，同样不满足终止条件，继续执行return n * factorial(n - 1)，需要计算factorial(3)。
   • 这个过程一直持续，直到计算factorial(1)。当n = 1时，满足终止条件，factorial(1)直接返回1。
   • 然后，递归调用开始返回。factorial(2)得到2*1 = 2（因为factorial(2)执行2*factorial(1)），factorial(3)得到3*2 = 6（因为factorial(3)执行3*factorial(2)），以此类推，最终factorial(5)得到5*4*3*2*1 = 120。
4. 递归的优点
   • 代码简洁：对于一些具有重复结构的问题，如树的遍历、斐波那契数列的计算等，递归可以使代码非常简洁。例如，计算斐波那契数列的函数：

展开过程

这段代码通过递归很直观地表达了斐波那契数列的定义：第n项等于第n - 1项和第n - 2项之和。

• 易于理解（对于某些问题）：当问题本身具有递归性质时，递归算法可以自然地反映问题的结构。例如，在树结构中，递归遍历（如先序遍历、中序遍历、后序遍历）就很好地利用了树的递归定义：树是由根节点、左子树和右子树组成的，左子树和右子树本身也是树。

1. 递归的缺点
   • 效率问题：递归函数可能会导致大量的函数调用开销。以斐波那契数列的递归计算为例，在计算fibonacci(n)时，会重复计算很多子问题。例如，计算fibonacci(5)时，fibonacci(3)会被计算两次，随着n的增大，重复计算的次数会呈指数增长，导致时间复杂度较高（斐波那契数列的递归计算时间复杂度为）。
   • 可能导致栈溢出：由于递归是通过函数调用栈来实现的，每次递归调用都会在栈中占用一定的空间。如果递归深度太深（例如，一个无限递归或者递归深度超过了栈的容量），就会导致栈溢出错误。例如，在一个栈空间有限的环境中，计算一个非常大的阶乘或者深度很深的树的遍历可能会出现这种情况。
2. 递归的应用场景
   • 树和图的遍历：如二叉树的先序、中序、后序遍历，图的深度优先搜索（DFS）等。以二叉树的先序遍历为例，先访问根节点，然后递归地访问左子树和右子树，代码如下：

展开过程

• 数学计算：如阶乘、斐波那契数列等计算。
• 分治算法：将一个大问题分解为多个小的子问题，分别解决子问题后再合并结果。例如，快速排序算法中的划分操作部分递归地对左右子数组进行排序，这也是一种分治思想的体现。