我们知道在一个函数内部是可以调用其他函数。那么如果一个函数在内部调用函数自身,这个函数就是递归函数。
执行递归函数将反复调用其自身,每调用一次就进入新的一层。如果一直调用那么就是一个死循环了,这样肯定是不对的,所以递归函数必须有终止条件。当函数在一直递归,直到遇到某个终止条件后返回。
所以递归要有两个要素,终止条件与递推关系。
递归的终止条件一般定义在递归函数内部,在递归调用前要做一个条件判断,根据判断的结果选择是继续调用自身,还是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也没有做优化,所以,即使把递归函数改成尾递归方式,也不支持尾递归优化,依然也会导致栈溢出。
其实尾递归实际上和循环是等价的,所以不支持尾递归优化的编程语言能用循环解决的,尽量不使用递归。