什么是递归？
「递归（Recursion)」 是一种解决问题的方法，它将问题分解为更小的子问题，并逐层解决这些子问题。递归算法的核心思想是：「一个函数可以直接或间接地调用自身」。通过这种自我调用，我们可以用简洁的代码来解决复杂问题。
满足递归的条件
一般来说，满足下面三个条件就可以使用递归：
- 待求解问题的解可以分解为多个子问题的答案。子问题就是数据规模更小的问题。
- 待求解问题与分解之后的问题，只有数据规模不同，求解思路完全相同。
- 存在递归终止的条件。递归问题必须得有终止条件，否则将会无限循环。
如何编写递归代码
编写递归代码的关键是将符合递归条件的问题公式化，将问题变成递推公式，寻找终止条件，然后根据公式“翻译”为代码。
例如斐波那契数列的问题：数列的前两项为1，从第三项开始，每一项都等于前两项之和，那么求解斐波那契数列的第
项则有：
为正整数
∈N
- 当
或
，值为1
- 当
时，则
则有
然后将上述公式“翻译”为代码，如下所示：
代码语言：javascript复制public int Fibonaci(uint n)
{
if (n > 0 && n <= 2) return 1;
return Fibonaci(n - 1) Fibonaci(n - 2);
}
所以，编写递归代码的关键就是找到将大问题分解为小问题的规律，并且基于此写出递推公式，然后找出终止条件，最后将公式"翻译"成代码。
递归的堆栈溢出问题
在函数调用会使用栈来保存临时变量，每调用一个新的函数，都会将临时变量封装为栈帧，压入内存栈，等函数执行完成后，再将栈帧出栈，所以，如果递归求解的数据规模很大，调用层次很深，一直往函数栈里添加数据，就会塞满函数栈，导致堆栈溢出。
如何避免出现堆栈溢出呢？「可以通过在代码中限制递归调用的最大深度」。
假设限制递归深度为1000，则修改后代码：
代码语言：javascript复制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) 这个值就被计算了三次。
为了避免重复，可以使用字典将计算过的值存储下来，当递归调用到已经计算过的值时，直接从字典中取值并返回，这样就省掉了重复计算。
将上文中的代码再进行优化：
代码语言：javascript复制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;
}
将递归代码改写为非递归代码
使用递归编程有利有弊，递归编程的好处是使用递归编写的代码的表达能力强，写起来简洁，而递归编程的劣势是空间复杂度高，且存在堆栈溢出和重复计算的问题，因此，在实际开发过程中，可以根据实际情况来决定是是否使用递归实现，例如可以将上述的斐波那契数列的代码改为非递归代码，如下所示：
代码语言：javascript复制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 [2] 斐波那契数列：https://en.wikipedia.org/wiki/Fibonacci_number ❞
