递归函数

定义:
在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。

特点:

• 必须有一个明确的结束条件；
• 每次进入更深一层递归时，问题规模相比上次递归都应有所减少
• 相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）。
• 递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）

例子:
计算1到100之间相加之和；通过循环和递归两种方式实现

# 循环方式 
def f1(n): 
    sum = 0 
    for i in range(1,n+1) : 
        sum += i 
    print(sum)

递归方式

def recu(n): 
    if n>0: 
       return n +recu(n-1) 
    else: 
       return 0 

f1(100) 
sum = recu(100) 
print(sum)

尾递归

解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。
尾递归是指，在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。
这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

计算1到100之间相加之和；使用尾递归实现

def recu1(n,count):
    if n>0:
       return recu1(n-1,count+n)
    else:
       return count

def wrecu(n):
    return recu1(n,0)` 

例子

使用递归方式实现阶乘：n=7
7654321

# 普通递归
def func1(n):
    if n==1:
        return 1
    else:
        return n*func(n-1)

# 尾递归
def fact1(n):
    return fact_iter(n, 1)

def fact_iter(num, total):
    if num == 1:
        return total
    return fact_iter(num - 1, num * total)` 

突破python迭代限制

python默认迭代次数不能超过996次，超过会报错
可以修改最大迭代次数来避免报错：

注意: 修改的次数 最好比 需要的迭代次数大 5次以上

import sys
sys.setrecursionlimit(2000)