#我们前面学习了在函数中返回函数，也学习了在一个函数中调用另一个函数，函数是否可以调用自己呢？答案是可以的。如果一个函数在内部调用自身那么这个函数就称作递归函数。
#递归函数的简单定义如下：
1 # /usr/bin/python3 2 #!-*-conding:UTF8 -*- 3 #递归函数 4 5 def recursion(): 6 recursion()
#这只是一个简单定义，执行并没有什么结果。
#当然，也可以尝试会发生什么，理论上会永远运行下去，但实际操作时可能不一会儿程序就崩溃了。因为每次调用函数都会用掉一点内存，在足够多的函数调用发生后，空间几乎被占满了，程序就会报异常。
#这类递归称作无穷递归（infinite recursion），理论上永远不会结束。当然，我们需要能实际做事情的函数，有用的递归函数应该满足如下条件：
（1）、当函数直接返回值时有基本实例（最小可能性问题）。
（2）、递归实例，包括一个或多个问题最小部分的递归调用。
#使用递归关键在于将问题分解为小部分，递归不能永远继续下去，因为他总是以最小可能性结束，而这些问题又存储在基本实例中。
#函数调用自身是怎么实现的？
#其实函数每次被调用时都会被创建一个新命名空间，也就是当函数调用“自身”时，实际上运行的是两个不同的函数（也可以说一个函数具有两个不同的命名空间）。
#我们来看一个递归示例，计算阶乘n!=1x2x3x...xn，用函数fact(n)表示，可以看出：
1 fact(n)=n!=1x2x3x...x(n-1)xn=(n-1)!xn=fact(n-1)xn
#所以，fact(n)可以表示为nxfact(n-1),只有n=1时需要特殊处理。
#于是，fact(n)用递归方式定义函数如下：
1 #! /usr/bin/python3 2 #-*-conding:UTF8 -*- 3 #递归函数 4 5 def fact(n): 6 if n==1: 7 return 1 8 return n*fact(n-1)
#执行该函数：
1 print('调用递归函数执行结果为：',fact(5))
#执行结果如下：
1 ==================== RESTART: C:/Users/L/Desktop/递归函数.py ==================== 2 调用递归函数执行结果为： 120
#由执行结果看到，函数已正确输出5的阶乘的结果。
#计算fact(5)时可以根据函数定义看到计算过程：
1 print('调用递归函数执行结果为：',fact(5)) 2 print('调用递归函数执行结果为：',5*fact(4)) 3 print('调用递归函数执行结果为：',5*(4*fact(3))) 4 print('调用递归函数执行结果为：',5*(4*(3*fact(2)))) 5 print('调用递归函数执行结果为：',5*(4*(3*(2*fact(1))))) 6 print('调用递归函数执行结果为：',5*(4*(3*(2*1)))) 7 print('调用递归函数执行结果为：',5*(4*(3*2))) 8 print('调用递归函数执行结果为：',5*(4*6)) 9 print('调用递归函数执行结果为：',5*24) 10 print('调用递归函数执行结果为：',120)
#由函数定义可以得知，递归函数的优点是定义简单、逻辑清晰。
#理论上，所有递归函数都可以写成循环的方式，不过循环的逻辑不如递归清晰。
#使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的。每当进入一个函数调用，栈就会加一层栈帧；每当函数返回，栈就会减一层栈帧。
#由于栈的大小是无限的，因此递归调用的次数过多会导致栈溢出。可以尝试一下fact(1000)，执行结果如下：
1 ==================== RESTART: C:/Users/L/Desktop/递归函数.py ==================== 2 Traceback (most recent call last): 3 File "C:/Users/L/Desktop/递归函数.py", line 10, in <module> 4 print('调用递归函数执行结果为：',fact(1000)) 5 File "C:/Users/L/Desktop/递归函数.py", line 8, in fact 6 return n*fact(n-1) 7 File "C:/Users/L/Desktop/递归函数.py", line 8, in fact 8 return n*fact(n-1) 9 File "C:/Users/L/Desktop/递归函数.py", line 8, in fact 10 return n*fact(n-1) 11 [Previous line repeated 989 more times] 12 File "C:/Users/L/Desktop/递归函数.py", line 6, in fact 13 if n==1: 14 RecursionError: maximum recursion depth exceeded in comparison
#由执行结果看到，执行出现异常，异常提示超过最大递归深度。
#这个问题需要如何解决？
#解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样，把循环看成是一种特殊尾递归函数也可以。
#尾递归是值在函数返回时调用函数本身，并且return语句不能包含表达式。这样，编译器或解释器就可以对尾递归进行优化，使递归本身无论调用多少次都只占用一个栈帧，从而避免栈溢出的情况。
#由于上面的fact(n)函数return n*fact(n-1)引入了乘法表达式，因此不是尾递归。要改成尾递归方式需要多一点代码，主要是把每一步乘积传入递归函数中，看如下函数定义方式：
1 #! /usr/bin/python3 2 #-*-conding:UTF8 -*- 3 #递归函数 4 5 def fact(n): 6 return fact_iter(n,1) 7 8 def fact_iter(num,product): 9 if num==1: 10 return product 11 return fact_iter(num-1,num*product)
#可以看到，return fact_iter(num-1,num*product)仅返回递归函数本身，num-1和num*product在函数调用前就会被计算，不影响函数调用。
#fact(5)对应的fact_iter(5,1)的调用如下：
1 ===>fact_iter(5,1) 2 ===>fact_iter(4,5) 3 ===>fact_iter(3,20) 4 ===>fact_iter(2,60) 5 ===>fact_iter(1,120) 6 ===>120
#执行该函数：
1 print('调用递归函数执行结果为：',fact_iter(5,1)) 2 print('调用递归函数执行结果为：',fact_iter(4,5)) 3 print('调用递归函数执行结果为：',fact_iter(3,20)) 4 print('调用递归函数执行结果为：',fact_iter(2,60)) 5 print('调用递归函数执行结果为：',fact_iter(1,120))
#执行结果如下：
1 调用递归函数执行结果为： 120 2 调用递归函数执行结果为： 120 3 调用递归函数执行结果为： 120 4 调用递归函数执行结果为： 120 5 调用递归函数执行结果为： 120
#由操作结果看到，调用尾递归时如果做了优化，栈就不会增长，因此无论多少次调用都不会导致栈溢出。