博客

Python中的递归是指函数内部调用自身的过程。在某些情况下，递归能够帮助我们更简洁、清晰地解决一些问题，而且比循环更加直观易懂。下面是Python中递归代替循环的使用方法攻略。

递归原理

递归的模型是一个递归树，我们需要明确递归函数的终止条件，从而避免陷入无限循环（无限递归）的情况。一般来说，我们要在设计递归函数时考虑两个方面：

1. 基线条件：指函数需要处理的最简单的情况。对于递归函数，这个条件通常应该放在递归函数的开始处。否则，递归函数将永远运行下去，栈最终会耗尽（我们一般称为进入了“递归深渊”）。
2. 递归条件：指函数调用自身的条件。

合理使用递归算法，可以让代码更加简洁易懂。

Python递归实例

下面我们分别以斐波那契数列和地狱塔问题为例，介绍递归的使用方法。

例1：斐波那契数列

斐波那契数列是一组数学上有意义的的数列，前两个数是0和1，从第三个数开始，每个数都是前两个数之和，如下所示:

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

代码如下：

def fib(n):
    if n <= 1:
        return n
    else:
        return (fib(n-1) + fib(n-2))

num = int(input("请输入一个正整数："))
if num <= 0:
    print("请输入一个正整数。")
else:
    print("斐波那契数列：")
    for i in range(num):
        print(fib(i), end=' ')

在上述代码中，我们定义了函数 fib(n) 用来计算斐波那契数列中的第n个数。我们在函数内部使用了递归的方式，当 n <= 1 时，递归结束。否则，递归调用 fib(n-1) 和 fib(n-2) 两个函数，从而实现了求出斐波那契数列中每一个数的功能。

下面是示例程序的运行结果：（此处输入的数字为9）

斐波那契数列：
0 1 1 2 3 5 8 13 21 

例2：地狱塔问题

地狱塔问题是一道很有名的数学问题，其题意是：你需要移动一个堆的圆盘，将其从第一根柱子上的铁钉移到第三根柱子上的铁钉，规则如下：

1. 你每次只能移动一个盘子。
2. 将一个盘子从任意一个位置移动到另外一个位置，都会计算为一步操作。
3. 你不能将一个较大的盘子摆在较小的盘子之上。

代码如下：

def hanoi(n, src, dest, mid):
    if n == 1:
        print("{}/{} -> {}".format(src, n, dest))
    else:
        hanoi(n-1, src, mid, dest)
        print("{}/{} -> {}".format(src, n, dest))
        hanoi(n-1, mid, dest, src)

n = int(input("请输入圆盘数目："))
print("移动步骤如下：")
hanoi(n, "A", "C", "B")

在上述代码中，函数 hanoi(n, src, dest, mid) 用来完成地狱塔问题。我们在函数内部使用了递归的方式，当 n == 1 时，递归结束。否则，递归调用函数 hanoi(n-1,src,mid,dest) 和 hanoi(n-1,mid,dest,src)，从而实现了圆盘移动的功能。

下面是示例程序的运行结果：（此处输入圆盘数为3）

请输入圆盘数目：3
移动步骤如下：
A/1 -> C
A/2 -> B
C/1 -> B
A/3 -> C
B/1 -> A
B/2 -> C
A/1 -> C