递归算法事例

一．例子（用从C＋＋描述）：

行号 程序

0 p (int w)

1 {if（ w>o）

2 { cout

3 p(w-1);

4 p(w-1);

5 }

6 }

结束

执行语句 p(4) 后的打印结果：4 3 2 1 1 2 1 1 3 2 1 1 2 1 1

二．说明：

1．递归调用与普通的调用原理相同，只不过是每次调用的函数都是自己本身。

2．我们完全可以自己编程设置堆栈（用户堆栈），来实现与“递归调用”相同的功能。

3． 3.在“递归调用”时，系统会自动设置和管理堆栈（系统堆栈），而

无需我们的干预，但这同时增加了“递归调用”的神秘性。为了更好

地 地理解“递归调用”，现将系统堆栈以表格的方式表示出来。

4．对于“堆栈”格式的一些说明

堆栈的格式为：

方格a
方格b
方格c

函数调用完返回的行号
调用的函数
W 的值

每调用一次函数就“入栈”一次；函数执行完了，就“出栈”一次

三．程序解释：

1．开始调用p(4)，此时执行的语句有：1、2、3

结束
P(4)
4

执行p(4)的语句2：cout

但是由于语句3，在执行过程中还要调用p(3)，只有p(3)执行完了，才能继续执行p(4)。

2．开始调用P(3)，此时执行的语句有：1、2、3

4
P(3)
3

结束
P(4)
4

当p（3）执行完了，就会执行p(4)中的语句4（所以在方格a中，填“4”）。

执行p(3)的语句2：cout

同上面的情况相同，当执行到语句3，还要调用p(2)，只有p(2)执行完了，才能继续执行p(3)。

3．开始调用P(2)，此时执行的语句有：1、2、3

4
P(2)
2

4
P(3)
3

结束
P(4)
4

执行p(2)的语句2：cout

同上面的情况相同，当执行到语句3，还要调用p(1)，只有p(1)执行完了，才能继续执行p(2)。

4．开始调用P(1)，此时执行的语句有：1、2、3

4
P(1)
1

4
P(2)
2

4
P(3)
3

结束
P(4)
4

执行p(2)的语句2：cout

同上面的情况相同，当执行到语句3，还要调用p(0)，只有p(0)执行完了，才能继续执行p(1)。

5．开始调用P(0)，此时执行的语句有：1

4
P(0)
0

4
P(1)
1

4
P(2)
2

4
P(3)
3

结束
P(4)
4

因为w＝0不满足语句1，所以直接跳到语句5、6，从而p(0)执行完毕，p(0)要进行“出栈”操作。

6．此时执行的语句有：4

4
P(1)
1

4
P(2)
2

4
P(3)
3

结束
P(4)
4

由于p(0)执行完成，且p(0)的方格a中为4，因此继续执行p(1)的语句4 ：p(w-1)； 又由于p(1)方格c中w值为1，所以调用p(0)。

7．开始调用p(0)

5
P(0)
0

4
P(1)
1

4
P(2)
2

4
P(3)
3

结束
P(4)
4

当p（0）执行完了，就会执行p(1)中的语句5（所以在方格a中，填“5”）。

因为w＝0不满足语句1，所以直接跳到语句5、6，从而p(0)执行完毕，p(0)要进行“出栈”操作。

8．此时执行的语句有：5

4
P(1)
1

4
P(2)
2

4
P(3)
3

结束
P(4)
4

由于p(0)执行完成，且p(0)的方格a中为5，因此继续执行p(1)的语句5 （最后一句），所以p(1)执行完毕，p(1)要进行“出栈”操作。

9．

4
P(2)
2

4
P(3)
3

结束
P(4)
4

由于p(1)执行完成，且p(1)的方格a中为4，因此继续执行p(2)的语句4 ：p(w-1)； 又由于p(2)方格c中w值为2，所以调用p(1)。

10．开始调用P(1)，此时执行的语句有：1、2、3

5
P(1)
1

4
P(2)
2

4
P(3)
3

结束
P(4)
4

当p（1）执行完了，就会执行p(2)中的语句5（所以在方格a中，填“5”）。

执行p(1)的语句2：cout

当执行到语句3，还要调用p(0)，只有p(0)执行完了，才能继续执行p(1)。

11．始调用P(0)，此时执行的语句有：1

4
P(0)
0

5
P(1)
1

4
P(2)
2

4
P(3)
3

结束
P(4)
4

因为w＝0不满足语句1，所以直接跳到语句5、6，从而p(0)执行完毕，p(0)要进行“出栈”操作。

12．此时执行的语句有：4

5
P(1)
1

4
P(2)
2

4
P(3)
3

结束
P(4)
4

由于p(0)执行完成，且p(0)的方格a中为4，因此继续执行p(1)的语句4 ：p(w-1)；又由于p(1)方格c中w值为1，所以调用p(0)。

13．开始调用p(0)

5
P(0)
0

5
P(1)
1

4
P(2)
2

4
P(3)
3

结束
P(4)
4

当p（0）执行完了，就会执行p(1)中的语句5（所以在方格a中，填“5”）。

因为w＝0不满足语句1，所以直接跳到语句5、6，从而p(0)执行完毕，p(0)要进行“出栈”操作。

14．此时执行的语句有：5

5
P(1)
1

4
P(2)
2

4
P(3)
3

结束
P(4)
4

由于p(0)执行完成，且p(0)的方格a中为5，因此继续执行p(1)的语句5 （最后一句），所以p(1)执行完毕，p(1)要进行“出栈”操作。

15．

4
P(2)
2

4
P(3)
3

结束
P(4)
4

由于p(1)执行完成，且p(1)的方格a中为5，因此继续执行p(2)的语句5 （最后一句），所以p(2)执行完毕，p(2)要进行“出栈”操作。

注意：其实步骤10～15重复了步骤4～9,因为它们都调用的P(1)

16．

4
P(3)
3

结束
P(4)
4

由于p(2)执行完成，且p(2)的方格a中为4，因此继续执行p(3)的语句4 ：p(w-1)； 又由于p(3)方格c中w值为3，所以调用p(2)。

17．开始调用P(2)，此时执行的语句有：1、2、3

5
P(2)
2

4
P(3)
3

结束
P(4)
4

当p（2）执行完了，就会执行p(3)中的语句5（所以在方格a中，填“5”）。

执行p(2)的语句2：cout

同上面的情况相同，当执行到语句3，还要调用p(1)，只有p(1)执行完了，才能继续执行p(2)。

18．开始调用p(1)

省略……

注意：其实步骤17～29重复了3～15,因为它们都调用的P(2)

在这步骤中，又打印了2 1 1（见步骤3、4、10）

四．结论与分析：

步骤
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

结果
4
3
2
1
1
2
1
1
3
2
1
1
2
1
1

第5个结果重复第4个结果，这是因为他们都调用了p(1)

第6、7、8个结果重复第3、4、5个结果，这是因为他们都调用了p(2)

第9～15个结果重复第2～8个结果，这是因为他们都调用了p(3)