**递归函数** 在上一章嵌套函数拆分之后，我们在函数内部调用了外部其他函数。如果一个函数在内部调用自身本身，那么这个函数就被称为递归函数。 递归函数定义简单，逻辑清晰。理论上，所有的递归函数都可以改写成循环结构。 在数学上我们求阶乘 ~~~ n! = n * (n-1) * ...*3*2*1 ~~~ 我们用函数 myFact(n) 表示 ~~~ myFact(n) = n! = n * (n-1) * ...*3*2*1 = n * (n-1)! = n * myFact(n-1) ~~~ 我们知道 1! 阶乘是 1 ，0! 阶乘也是 1，所以当 n = 1 与 0 时，就需要进行特殊处理了 函数如下 ~~~ #!/usr/bin/env python3 # -*- coding:utf-8 -*- def myFact(n): if not isinstance(n,int) : return '%s is error type' % n if n < 0 : return 'parameter is not less than 0' if n < 2 : return 1 return n * myFact(n-1) print(myFact('123')) #第一次调用 print(myFact(-1)) #第二次调用 print(myFact(0)) #第三次调用 print(myFact(5)) #第四次调用 ~~~ 调用结果 ~~~ 123 is error type #第一次调用结果 parameter is not less than 0 #第二次调用结果 1 #第三次调用结果 120 #第四次调用结果 ~~~ 递归特性 1. 必须有一个明确的结束条件。 2. 递归每深入一层，问题规模相比上次递归都应有所减少。 3. 递归效率不高，程序中能不用递归就不用。 **递归函数需要注意防止栈溢出。** 什么叫栈：又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。 栈，我们可以通俗理解为水桶，只能从一端进出水，"先进后出" 原则。 图片示意  在计算机中，函数调用是通过栈（stack）这种数据结构实现的，在调用一个函数的时候栈就会加一层，在函数返回的时候，栈就会减一层。由于栈的大小不是无限的，所以，如果递归调用的次数过多，就会导致栈溢出。 当调用并打印 print(myFact(999))，就出现了栈溢出 ~~~ airvip@airvip:/mnt/e/workspace/pylearn$ ./test.py Traceback (most recent call last): File "./test.py", line 18, in <module> print(myFact(999)) ... File "./test.py", line 12, in myFact return n * myFact(n-1) File "./test.py", line 8, in myFact if n < 0 : RecursionError: maximum recursion depth exceeded in comparison ~~~ 那如何解决因多次调用造成的栈溢出呢？ 我们可以通过 **尾递归** 进行优化，实际上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。 尾递归：在函数返回的时候，只是调用自己本身，并且 return 语句不能包含表达式。这样编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。 上面的 myFact(n) 函数由于 return n * myFact(n-1) 引入了乘法表达式，所以就不是尾递归了。要改成尾递归方式，主要是要把每一步的乘积传入到递归函数中 ~~~ #!/usr/bin/env python3 # -*- coding:utf-8 -*- def fact(n): if not isinstance(n,int) : return '%s is error type' % n if n < 0 : return 'parameter is not less than 0' return fact_iter( n) def fact_iter(count,res=1): if count < 2: return res return fact_iter(count - 1,res * count,) ~~~ 可以看到，return fact_iter(res * count, count - 1) 返回的是递归函数本身，每个参数在函数调用前就会被计算，不影响函数调用。 fact(5) 对应的 fact_iter(5, 1) 的调用如下： ~~~ 第一次调用 ： fact_iter(5,1) 第二次调用 ： fact_iter(4,5) 第三次调用 ： fact_iter(3,20) 第四次调用 ： fact_iter(2,60) 第五次调用 ： fact_iter(1,120) 第六次调用 ：120 ~~~ 尾递归调用时，如果做了优化，栈不会增长，因此，无论多少次调用也不会导致栈溢出。 遗憾的是，大多数编程语言没有针对尾递归做优化，Python解释器也没有做优化，所以，即使把上面的 fact(n) 函数改成尾递归方式，也会导致栈溢出。 有一个针对尾递归优化的装饰器 (decorator),大家可以参考下 ~~~ #!/usr/bin/env python2.4 # This program shows off a python decorator( # which implements tail call optimization. It # does this by throwing an exception if it is # it's own grandparent, and catching such # exceptions to recall the stack. import sys class TailRecurseException: def __init__(self, args, kwargs): self.args = args self.kwargs = kwargs def tail_call_optimized(g): """ This function decorates a function with tail call optimization. It does this by throwing an exception if it is it's own grandparent, and catching such exceptions to fake the tail call optimization. This function fails if the decorated function recurses in a non-tail context. """ def func(*args, **kwargs): f = sys._getframe() if f.f_back and f.f_back.f_back \ and f.f_back.f_back.f_code == f.f_code: raise TailRecurseException(args, kwargs) else: while 1: try: return g(*args, **kwargs) except TailRecurseException, e: args = e.args kwargs = e.kwargs func.__doc__ = g.__doc__ return func @tail_call_optimized def factorial(n, acc=1): "calculate a factorial" if n == 0: return acc return factorial(n-1, n*acc) print factorial(10000) # prints a big, big number, # but doesn't hit the recursion limit. @tail_call_optimized def fib(i, current = 0, next = 1): if i == 0: return current else: return fib(i - 1, next, current + next) print fib(10000) # also prints a big number, # but doesn't hit the recursion limit. ~~~