递归算法能够重复性的将问题分解为同类的子问题,然后解决这些子问题,最终达到解决最开始的问题为目的。以下从解决“阶乘”问题、“汉诺塔”问题、“斐波那契数列”问题、“最大公倍数和最小公约数”问题、“小球弹跳”、“深度优先”与“广度优先”问题等六个经典递归算法的案例进行介绍:
一、解决“阶乘”问题
阶乘是基斯顿·卡曼(Christian Kramp,1760~1826)于 1808 年发明的运算符号,是一个正整数的阶乘(factorial)是所有小于及等于正整数的积,并且0的阶乘为1。自然数n的阶乘写作n!。
亦即n!=1×2×3×...×(n-1)×n。阶乘亦可以递归方式定义:0!=1,n!=(n-1)!×n。
N的阶乘就是N*fact(N-1),具体代码如下:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
# 测试
num = 5
print(f"{num}的阶乘是:{factorial(num)}")
二、解决“汉诺塔”问题
汉诺塔来之一个印度古老传说,大体意思是:寺庙有三根柱子,在一根柱子上从下往上按照大小顺序摞着64片圆盘,现状需要把圆盘从下面开始按大小顺序重新摆放在另一根柱子上,并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
hanoi
函数使用递归的方式解决汉诺塔问题。它接受四个参数:n