请注意,本文编写于 303 天前,最后修改于 294 天前,其中某些信息可能已经过时。

目录

什么是递归?
满足递归的条件
如何编写递归代码
递归的堆栈溢出问题
递归的重复计算问题
将递归代码改写为非递归代码
总结

什么是递归?

递归(Recursion) 是一种解决问题的方法,它将问题分解为更小的子问题,并逐层解决这些子问题。递归算法的核心思想是:一个函数可以直接或间接地调用自身。通过这种自我调用,我们可以用简洁的代码来解决复杂问题。

满足递归的条件

一般来说,满足下面三个条件就可以使用递归:

  • 待求解问题的解可以分解为多个子问题的答案。子问题就是数据规模更小的问题。
  • 待求解问题与分解之后的问题,只有数据规模不同,求解思路完全相同。
  • 存在递归终止的条件。递归问题必须得有终止条件,否则将会无限循环。

如何编写递归代码

编写递归代码的关键是将符合递归条件的问题公式化,将问题变成递推公式,寻找终止条件,然后根据公式“翻译”为代码。

例如斐波那契数列的问题:数列的前两项为1,从第三项开始,每一项都等于前两项之和,那么求解斐波那契数列的第nn项则有:

  • nn为正整数 nn∈N
  • n=1n=1n=2n=2,值为1
  • n>2n>2时,则f(n)=f(n1)+f(n2)f(n)=f(n-1)+f(n-2)

则有

f(x)={10<x2f(x1)+f(x2)x>2xN f(x) = \begin{cases} 1 & 0< x\leq 2 \\ f(x-1)+f(x-2) & x>2 \end{cases}\qquad x∈N

然后将上述公式“翻译”为代码,如下所示:

csharp
public int Fibonaci(uint n) { if (n > 0 && n <= 2) return 1; return Fibonaci(n - 1) + Fibonaci(n - 2); }

所以,编写递归代码的关键就是找到将大问题分解为小问题的规律,并且基于此写出递推公式,然后找出终止条件,最后将公式"翻译"成代码。

递归的堆栈溢出问题

在函数调用会使用栈来保存临时变量,每调用一个新的函数,都会将临时变量封装为栈帧,压入内存栈,等函数执行完成后,再将栈帧出栈,所以,如果递归求解的数据规模很大,调用层次很深,一直往函数栈里添加数据,就会塞满函数栈,导致堆栈溢出。

如何避免出现堆栈溢出呢?可以通过在代码中限制递归调用的最大深度

假设限制递归深度为1000,则修改后代码:

csharp
static int depth = 0; public static int Fibonaci(uint n) { depth++; if (depth > 1000) throw new Exception("超出递归范围!"); if (n > 0 && n <= 2) return 1; return Fibonaci(n - 1) + Fibonaci(n - 2); }

递归的重复计算问题

除堆栈溢出问题外,编写递归还会出现重复计算的问题,例如上述斐波那契数列的递归,在执行时就有重复计算的问题。

例如,当计算 Fibonaci(5) 的时候,需要计算 Fibonaci(4)Fibonaci(3),而计算 Fibonaci(4) 又需要计算 Fibonaci(3)Fibonaci(2),以此类推。因此,Fibonaci(3) 这个值就被计算了两次,Fibonaci(2) 这个值就被计算了三次。

为了避免重复,可以使用字典将计算过的值存储下来,当递归调用到已经计算过的值时,直接从字典中取值并返回,这样就省掉了重复计算。

将上文中的代码再进行优化:

csharp
static int depth = 0; static Dictionary<uint, int> ValuePairs = new Dictionary<uint, int>(); public static int Fibonaci(uint n) { depth++; if (depth > 1000) throw new Exception("超出递归范围!"); if (n > 0 && n <= 2) return 1; if (ValuePairs.ContainsKey(n)) { return ValuePairs[n]; } var res = Fibonaci(n - 1) + Fibonaci(n - 2); ValuePairs.Add(n, res); return res; }

将递归代码改写为非递归代码

使用递归编程有利有弊,递归编程的好处是使用递归编写的代码的表达能力强,写起来简洁,而递归编程的劣势是空间复杂度高,且存在堆栈溢出和重复计算的问题,因此,在实际开发过程中,可以根据实际情况来决定是是否使用递归实现,例如可以将上述的斐波那契数列的代码改为非递归代码,如下所示:

csharp
public static int Fibonaci(uint n) { if (n > 0 && n <= 2) return 1; int prev = 1; int prev_prev = 1; int result = 0; for (int i = 2; i < n; i++) { result = prev + prev_prev; prev_prev = prev; prev = result; } return result; }

所有递归算法都可以改写为迭代循环的非递归写法吗?

是,理论上所有递归算法都可以改写为迭代循环的非递归写法。这是因为递归算法本质上是一个函数在自己内部不断调用自己,而迭代循环可以通过变量的更新来达到相同的效果。

具体来说,可以通过使用一个栈或队列等数据结构来模拟递归函数的调用过程。每当递归函数需要调用自身时,将当前的参数值和程序计数器等信息保存到栈或队列中,然后继续执行下一个语句。当递归函数返回时,从栈或队列中弹出保存的信息,恢复之前的状态,并继续执行之前被中断的语句。

虽然理论上可以将所有递归算法改写为迭代循环的非递归写法,但实际上有些算法可能更适合使用递归实现,而另一些算法则更适合使用迭代循环实现。例如,递归算法通常在树形结构的遍历和图形搜索等算法中使用,而迭代循环则更适合处理数值计算等需要大量循环迭代的算法。

总结

递归式一种高效,简洁的编码模式,只要满足递归的3个条件,就可以使用递归算法去实现。不过,递归代码比较难写,难理解。编写递归代码的关键是不要试图去模拟计算机递归调用的过程,正确的编写方式是写出递推公式,找出终止条件,然后"翻译"为代码。

递归也有它自己的弊端,比如堆栈溢出,重复计算,函数调用耗时多和空间复杂度高,所以在编写递归算法代码时,要避免出现这些问题。

参考资料

[1] 数据结构与算法之美 / 王争 著. --北京:人民邮电出版社,2021.6

本文作者:Peter.Pan

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!