递归算法例解(一)

王朝other·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

递归算法例解(一)

这个递归程序很简单,但是遇到复杂的递归算法可就不容易看懂了。以下这种方法能够帮助大家进行分析,但愿吧。

一.例子(用从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)。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航