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