示例1:计算阶乘是递归程序设计的一个经典示例
def fact(n):
if n == 1:
return 1
else:
return n * fact(n-1)
print(fact(5)) #res = 120
这里,当n == 1 时 非常重要,因为,这个条件是该递归程序的边界,也就是结束往下递归的条件。
可见,只要初始值大于零,这个函数就能够终止。停止的位置称为 基线条件(base case)。基线条件是递归程序的 最底层位置,在此位置时没有必要再进行操作,可以直接返回一个结果。所有递归程序都必须至少拥有一个基线条件,而且 必须确保它们最终会达到某个基线条件;否则,程序将永远运行下去,直到程序缺少内存或者栈空间。
递归程序的基本步骤
每一个递归程序都遵循相同的基本步骤:
- 初始化算法。递归程序通常需要一个开始时使用的种子值(seed value)。要完成此任务,可以向函数传递参数,或者提供一个入口函数, 这个函数是非递归的,但可以为递归计算设置种子值。
- 检查要处理的当前值是否已经与基线条件相匹配。如果匹配,则进行处理并返回值。
- 使用更小的或更简单的子问题(或多个子问题)来重新定义答案。
- 对子问题运行算法。
- 将结果合并入答案的表达式。
- 返回结果。
循环和递归函数对比
特性 | 循环 | |
重复 | 为了获得结果,反复执行同一代码块;以完成代码块或者执行 | 为了获得结果,反复执行同一代码块;以反复调用自己为信号而实现重复执行。 |
终止条件 | 为了确保能够终止,循环必须要有一个或多个能够使其终止的条件,而且必须保证它能在某种情况下满足这些条件的其中之一。 | 为了确保能够终止,递归函数需要有一个基线条件,令函数停止递归。 |
状态 | 循环进行时更新当前状态。 | 当前状态作为参数传递。 |
可见,递归函数与循环有很多类似之处。实际上,可以认为循环和递归函数是能够相互转换的。 区别在于,使用递归函数极少被迫修改任何一个变量 —— 只需要将新值作为参数传递给下一次函数调用。 这就使得您可以获得避免使用可更新变量的所有益处,同时能够进行重复的、有状态的行为。
递归函数
递归(Recursion),在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。
在使用递归时,需要注意以下几点:
- 递归就是在过程或函数里调用自身
- 必须有一个明确的递归结束条件,称为递归出口。
注意: 切勿忘记递归出口,避免函数无限调用。
def fact(n):
if n == 1:
return 1
else:
return n * fact(n-1)
print(fact(5)) #res = 120
为了明确递归步骤,对 5!
进行过程分解:
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 次调用返回
当数字减少到 1 时,递归结束。
递归的优缺点
从“编程之美”的角度来看,引用一句伟大的计算机编程名言:
To iterate is human,to recurse divine.
迭代者为人,递归者为神。
– L. Peter Deutsch
优点:
- 递归使代码看起来更加整洁、优雅
- 可以用递归将复杂任务分解成更简单的子问题
- 使用递归比使用一些嵌套迭代更容易
缺点:
- 递归的逻辑很难调试、跟进
- 递归调用的代价高昂(效率低),因为占用了大量的内存和时间。