python递归函数

递归函数简单来说就是函数的自我调用。使用递归函数很多时候可以使得代码简洁，优雅。可以把复杂的问题分解成简单的子问题。递归有无与伦比的魅力，从著名的计算机名言就可以看出递归的奇妙：

To iterate is human,to recurse divine. 
迭代者为人，递归者为神。 
– L. Peter Deutsch

　　其实上面这句话有点夸张了，递归不是完美的，它也有致命的弱点，那就是执行效率低，而且容易导致栈溢出（超过一千次）。　

　下面我们从一副美妙的图来直观的体会一下递归。

我们用一个简单的实例来比较一下递归和迭代的区别：求N的阶乘

使用迭代的方法如下：

def jiecheng(n):
    result=1
    for i in range(n) :
        result*=(i+1)
    print('%d的阶乘为%d'%(n,result))

jiecheng(5)    #5的阶乘为120

使用递归的方法如下：

def jiecheng(n):
    if n==1:
        return 1
    else:
        return n*(jiecheng(n-1))

可以看出使用递归可以让代码更加简洁优雅，更加具有数学美。

下面再通过斐波那契数列来探讨一下递归：

1、通过循环实现：

a=0
b=1
while b < 100:
    print(b)
    a, b = b, a+b

2、普通递归实现斐波那契数列：

1 ls=[]
2 for i in range(10):
3     if i==0 or i ==1:
4         ls.append(1)
5     else:
6         ls.append(ls[i-2]+ls[i-1])
7 print(ls)  #[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

3、通过尾递归方式实现：

def fbnq(n,a,b):
    if n==0:
        return (b)
    else:
        return fbnq(n-1,b,a+b)
print([fbnq(i,0,1) for i in range(5)])

这三种方法迭代效率其实是最高的，然后

python递归函数

推荐阅读