Python 进阶：递归算法的关键点剖析（阶乘，斐波那契数列案例）

• 2020 年 4 月 19 日
• AI
• Python, 算法

Python 中，递归是一种很多人都头晕的算法。
那在使用这个算法的时候，怎样可以更好地捋清楚思路呢？

首先我们来看案例：

一、求阶乘

传统实现方式：

def fact_for (x):
    r = 1
    for i in range(1,x+1):
        r *= i
    return r

递归实现方式：

def fact (x):
    if x!=1:
        r = x*fact(x-1)
        return r
    else:
        return x

二、斐波那契数列

传统实现方法：

def fibonacci_for (x):
    if x < 1:
        return 0
    elif x == 1:
        return 1
    elif x == 2:
        return 1
    else:
        a = 1
        b = 1
        for i in range(2,x):
            c = a+b
            a,b = b,c
        return c

递归实现方式：

def fibonacci (x):
    if x < 1:
        return 0
    elif x == 1:
        return 1
    elif x == 2:
        return 1
    else:
        return fibonacci (x-1)+fibonacci (x-2)

三、递归的要点分析

1. 递归需要函数自己调用自己

比如前面 r = x*fact(x-1) 语句，和 fibonacci (x-1)+fibonacci (x-2) 语句。

2. 递归需要有个停止条件（防止无限递归）

比如求阶乘的时候，当计算到 1 的时候，就要结束了。

3. 递归需要关注通项式

比如斐波那契数列的核心，就是第 n 个元素的值，为 n-1 和 n-2 这两个值的和。

4. 注意点

Python 中默认的递归最大层数应该是 100 层。
当我们需要超过这个层数的时候，可以用以下语句设置：

import sys
sys.setrecursionlimit(100)

后面找时间再多补充几个案例，请期待。。。