聊聊递归函数

我们知道在一个函数内部是可以调用其他函数。那么如果一个函数在内部调用函数自身，这个函数就是递归函数。

执行递归函数将反复调用其自身，每调用一次就进入新的一层。如果一直调用那么就是一个死循环了，这样肯定是不对的，所以递归函数必须有终止条件。当函数在一直递归，直到遇到某个终止条件后返回。

所以递归要有两个要素，终止条件与递推关系。

递归的终止条件一般定义在递归函数内部，在递归调用前要做一个条件判断，根据判断的结果选择是继续调用自身，还是return；返回终止递归。

终止的条件：

1、判断递归的次数是否达到某一限定值

2、判断运算的结果是否达到某个范围等，根据设计的目的来选择

在递归的时候，每次调用一个函数，计算机都会为这个函数分配新的空间，这就是说，当被调函数返回的时候，调用函数中的变量依然会保持原先的值，否则也不可能实现反向输出。

举个例子，我们初中的时候经常遇到的一个题型就是计算阶乘n! = 1 x 2 x 3 x ... x n，用函数fact(n)表示，可以看出：

fact(n)=n!=1×2×3×⋅⋅⋅×(n−1)×n=(n−1)!×n=fact(n−1)×n
复制代码

所以，fact(n)可以表示为n x fact(n-1)，在初中解题的时候我们还知道只有n=1时需要特殊处理。

计算n的阶乘的代码实例：

/** 
  * @Title: java版本
  * @Description: 计算n的阶乘 
  * @param n 0的阶乘是1
  * @author jiangxia
  * @date 2021年10月12日
  */
  public static long fact(int n) {
    if (n == 0) {
      return 1;
    }else {
      return n*fact(n-1);
    }
  }
复制代码

/** 
  * @Title: python版本
  * @Description: 计算n的阶乘 
  * @param n 0的阶乘是1
  * @author jiangxia
  * @date 2021年10月12日
*/
def fact(n):
    if n==1:
        return 1
    return n * fact(n - 1)
复制代码

比如fact(6)的运算过程就是：

6 * (5 * (4 * (3 * (2 * 1)))))
6 * (5 * (4 * (3 * 2))))
6 * (5 * (4 * 6)))
//......
720 // <= 最终的结果
复制代码

所以递归函数特点可以总结如下：

1、每一级函数调用时都有自己的变量，但是函数代码并不会得到复制，如计算5的阶乘时每递推一次变量都不同；

2、每次调用都会有一次返回，如计算5的阶乘时每递推一次都返回进行下一次；

3、递归函数中，位于递归调用前的语句和各级被调用函数具有相同的执行顺序；

4、递归函数中，位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反；

5、递归函数中必须有终止语句。

递归函数的优点：

递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。

比如上面求阶乘的代码如果用循环来写就是：

/** 
  * @Title: java版本
  * @Description: 计算n的阶乘的循环版本
  * @param n 0的阶乘是1
  * @author jiangxia
  * @date 2021年10月12日
  */
  public static long fact(int n) {
    long result = 1;
    for (int i=1; i<=n; i++) {
      result = result*i;
    }
    return result;
  }
复制代码

使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。可以试试fact(1000)。

解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。

函数在尾位置调用自身或是一个尾调用本身的其他函数等等，并且return语句不能包含表达式，则称这种情况为尾递归。尾递归也是递归的一种特殊情形。即在尾部直接调用自身的递归函数。对尾递归的优化也是关注尾调用的主要原因。尾调用不一定是递归调用，但是尾递归特别有用，也比较容易实现。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

比如上面的fact(n)函数由于最后的return n * fact(n - 1)引入了乘法表达式，所以就不是尾递归了。要改成尾递归方式，需要多一点代码，主要是要把每一步的乘积传入到递归函数中，但不是所有语言的编译器都做了尾递归优化。比如c实现了，JAVAhe python没有去实现尾递归优化。

def fact(n, m=1):
    if n == 0:
        return m
    return factorial(n - 1, n * m)
复制代码

可以看到，return factorial(n - 1, n * m)仅返回递归函数本身，n - 1和n * m在函数调用前就会被计算，不影响函数调用。

尾递归调用时，如果做了优化，栈不会增长，因此，无论多少次调用也不会导致栈溢出。

但是前面说过大多数编程语言没有针对尾递归做优化，Python和java也没有做优化，所以，即使把递归函数改成尾递归方式，也不支持尾递归优化，依然也会导致栈溢出。

其实尾递归实际上和循环是等价的，所以不支持尾递归优化的编程语言能用循环解决的,尽量不使用递归。