VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > Python基础教程 >
  • Python递归算法详解

递归的概念很简单,如果函数包含了对其自身的调用,该函数就是递归的。

递归(Recursion),在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。

在使用递归时,需要注意以下几点:

递归就是在过程或函数里调用自身

必须有一个明确的递归结束条件,称为递归出口。

注意: 切勿忘记递归出口,避免函数无限调用。

递归基本步骤

每一个递归程序都遵循相同的基本步骤: 

1.初始化算法。递归程序通常需要一个开始时使用的种子值(seed value)。要完成此任务,可以向函数传递参数,或者提供一个入口函数,这个函数是非递归的,但可以为递归计算设置种子值。 

2.检查要处理的当前值是否已经与基线条件相匹配(base case)。如果匹配,则进行处理并返回值。 

3.使用更小的或更简单的子问题(或多个子问题)来重新定义答案。 

4.对子问题运行算法。 

5.将结果合并入答案的表达式。 

6.返回结果。

 

基线条件(base case)。基线条件是递归程序的最底层位置,在此位置时没有必要再进行操作,可以直接返回一个结果。所有递归程序都必须至少拥有一个基线条件,而且必须确保它们最终会达到某个基线条件;否则,程序将永远运行下去,直到程序缺少内存或者栈空间。

主要应用范围

递归算法一般用于解决三类问题:

(1)数据的定义是按递归定义的。(比如Fibonacci函数)

(2)问题解法按递归算法实现。(回溯)

(3)数据的结构形式是按递归定义的。(比如树的遍历,图的搜索)  

典型的算法

大多数学过数学、计算机科学或者读过编程相关书籍的人,想必都会遇到阶乘:

n! = 1 × 2 × 3 × … × n

也可以用递归方式定义:

n! = (n-1)! × n

其中,n >= 1,并且 0! = 1。

由于简单、清晰,因此其常被用作递归的示例。

PS: 除了阶乘以外,还有很多算法可以使用递归来处理,例如:斐波那契数列、汉诺塔等。

 

非递归实现

1
2
3
4
5
def factorial(n):
    result = 1
    for in range(2, n+1):
        result *= i
    return result

阶乘函数的递归实现

1
2
3
def factorial(n):
    if == 0 or == 1return 1
    elsereturn (n * factorial(n - 1))

递归过程

为了明确递归步骤,对 5! 进行过程分解:

1
2
3
4
5
6
7
8
9
10
factorial(5)                        # 第 1 次调用使用 5
5 * factorial(4)                    # 第 2 次调用使用 4
5 * (4 * factorial(3))              # 第 3 次调用使用 3
5 * (4 * (3 * factorial(2)))        # 第 4 次调用使用 2
5 * (4 * (3 * (2 * factorial(1))))  # 第 5 次调用使用 1 
5 * (4 * (3 * (2 * 1)))             # 从第 5 次调用返回
5 * (4 * (3 * 2))                   # 从第 4 次调用返回
5 * (4 * 6)                         # 从第 3次调用返回
5 * 24                              # 从第 2 次调用返回
120                                 # 从第 1 次调用返回

相关教程