递归

递归

• 如果一个函数在内部调用了自身，这个函数称为递归函数
• 递归条件：

1.子问题与原始问题为同样的事，且更为简单
2.不能无限制的调用本身，要有个出口，化简为非递归状况处理

• 高斯求和问题：

    def sum_number(n):
        total = 0
        for i in range(0,n+1):
            total += i
    sum_number(100)

如果用递归来写：

    def sum_number(n):
        if n<=0:
            return 0
        return n+sum_number(n-1)
    sum_number(100)

• 递归核心：每一次递归，整体问题都要比原来减小，并且递归到一定层次时，要能直接给出结果。
• 基本步骤：

1.初始化算法。递归程序通常需要一个开始时使用的种子值，可以向函数传递参数，或者提供一个入口函数，这个函数是非递归的，但可以为递归计算设置种子值。
2.检查要处理的当前值是否已经与基线条件匹配。如果匹配，则进行处理并返回值
3.使用更小的或者更简单的子问题来重新定义答案。
4.对子问题进行算法
5.将结果合并入答案的表达式
6.返回结果

• 注意：使用递归函数要放置递归深度溢出，在Python中，通常情况下，这个深度为1000层，超过将抛出异常。在计算机中，函数递归调用是通过栈（stack）这种数据结构实现的，每当进入一个递归时，栈就会加一层，每当函数返回一次，栈就减少一层。由于栈的大小不是无线的，所以，递归调用的次数过多，会导致栈溢出。

尾递归

• 简介：

1.当递归调用是整个函数体最后执行的语句且它的返回值不属于表达式的一部分时，就是尾递归
2.特点：在回归过程中不做任何操作。
3.原理：当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。实际运行效率更高。

• 以尾递归方式实现阶乘函数：

    def facttail(n,res):
        if n < 0:
            return 0
        elif n == 0:
            return 1
        elif n == 1:
            return res
        else:
            return facttail(n-1,n*res)

只是比递归多了一个参数res。res（初始化为1）维护递归层次的深度。

匿名函数