一、什么时递归函数
在函数内部，可以调用其他函数，如果一个函数在内部调用自己本身，这个函数就叫做递归函数。
def fn(n): if n == 1: return 1 return n*fn(n-1) res = fn(5) print(res) 结果：120
上面的计算过程是什么样的呢？
fn(5) 5*fn(4) 5*(4*fn(3)) 5*(4*(3*fn(2))) 5*(4*(3*(2*fn(1)))) 5*(4*(3*(2*1))) 5*(4*(3*2)) 5*(4*6) 5*24 120
再看一个例子：
def calc(n): n = int(n/2) print(n) if n>0: calc(n) print(n) calc(10) 结果： 5 2 1 0 0 1 2 5
函数在进入下一层时，当前层的函数并未结束，它必须等它调用的下一层函数执行完毕才能返回，所以外层的print(n)一直在等着内层函数执行完毕才进行打印，外层的打印，也就是最下面那句print(n)会等最里层函数执行完毕后才会执行，然后不断地往外退层，所以才会出现0、1、2、5的效果。
二、递归的特性
1、必须有一个明确的结束条件。
2、每次进入更深一层递归时，问题规模相比上一次递归都应有所减少。
3、递归效率不高，递归层数过多会导致栈溢出（在计算机中，函数i盗用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会增加一层栈帧，每当函数返回，栈就会减少一层栈帧。由于栈的大小不是无限的，所以递归调用过多会导致栈溢出。
def fn(n): if n == 1: return 1 return n*fn(n-1) res = fn(1000) print(res) 结果： RecursionError: maximum recursion depth exceeded in comparison
原文：https://www.cnblogs.com/feixiangshuoshuo/p/12452377.html