Python 学习笔记 之 day6 递归函数

##递归函数看的云里雾里，廖雪峰大师给出的练习题我也没搞懂，先mark下理解的，其他的后续再说……

 

通过之前的学习已经知道，函数的内部是可以调用其他函数的，如果一个函数在内部调用自身本身，那么这个函数就是递归函数。

定义一个计算阶乘n！的函数
    n!= 1x2x3x4x……xn,用函数来表示可以看出
    jx(n)= n! = 1 x 2 x 3 x ... x (n-1) x n = (n - 1)! x n = jx(n-1) x n
    所以jx(n)可以表示为 jx(n-1) x n ，但是当n=1时，就不行了。因此需要额外处理一下n = 1 的情况。于是 阶乘用递归方式写出来就是：
   
        def jx(n):
            if n == 1:
                return 1
            return n * jx(n - 1)
           
递归函数定义简单，逻辑清晰，理论上所有的递归函数都可以写成循环的方式，但是循环的逻辑不如递归清晰。

栈溢出
    使用递归函数需要注意防止栈溢出， 函数调用是通过栈stack这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以当递归调用的次数过多时，就会导致栈溢出。

        jx(1000)
        RecursionError: maximum recursion depth exceeded in comparison
       
尾递归优化
    解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。
   
    尾递归是指在函数返回的时候，调用自身本身，并且return语句不能包含表达式。这样编译器或者解释器就可以把尾递归做优化，使递归无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。
   
    例：
   
    在前面的例子里，由于  return n * jx(n - 1) 引用了乘法表达式，所以就不是尾递归。要使用尾递归方式没主要是要把每一步的乘积传入到递归函数中。
        def jx(n):
            return jx_iter(n, 1)
           
        def jx_iter(num,r1):
            if num == 1:
                return r1
            return jx_iter(num - 1, num * r1)       #返回本次计算结果给函数本身，进入下一轮循环。
           
    尾递归调用时如果做了优化，栈不会增长，因此无论多少次调用也不会导致栈溢出。但是说这么多，在试验上面这个尾递归优化的例子时，发现python3依然会报错，因为……Python解释器也没做尾递归优化。
           
递归函数小结：
   1.  使用递归函数的优点时逻辑简单清晰，缺点是过深的调用会导致栈溢出。
   2.  针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的，没有循环语句的变成语言只能通过尾递归实现循环。
   3.  python标准的解释器没有针对尾递归做优化，任何递归函数都存在栈溢出的问题。