递归算法事例

发布时间:2017-09-03 13:07:35
递归算法事例

一.例子(用从C++描述):

行号 程序

0 p (int w)

1 {if( w>o)

2 { cout<<w;

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<<w;打印4(这是第一个结果)

但是由于语句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<<w; 打印3(这是第二个结果)

同上面的情况相同,当执行到语句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<<w;打印2(这是第三个结果)

同上面的情况相同,当执行到语句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<<w;打印1(这是第四个结果)

同上面的情况相同,当执行到语句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

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:襄阳SEO http://xiangyang.4567w.com