递归在编程中的妙用

开篇：润墨网以专业的文秘视角，为您筛选了一篇递归在编程中的妙用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

[摘要] 在子程序内直接或间接调用了它本身,就叫做递归调用,简称递归。要理解递归,必须用程序跟踪的方法,执行每一步、理解每一步,你会理解递归的过程。

[关键词] 调用 递归 记忆化

笔者在近20年的计算机专业的教学实践中,程序设计是主旋律,程序设计中递归是教与学的难点。对此,笔者做如下分析探讨。

一、对递归的理解至关重要

简而言之,在子程序内直接或间接调用了它本身,就叫做递归调用,简称递归。

如vb程序

private subcommand1_click

Call command1_click

end sub

要理解递归,必须用程序跟踪的方法,执行每一步、理解每一步,你会理解递归的过程。

Pascal程序

Procedure desolve( num : integer);

Begin

If num >0 then

Begin

Write ( num mod 10); Desolve( num div 10 ); Write(’ ‘)

end

End;

跟踪运行:

主程序

desolve( 123 )

1.参数变量取值: num (123

2.进入if语句条件为真(输出3(desolve(12) ,第一次递归调用,记住,语句write(‘ ‘) 还没有执行到,当第一次递归结束时,返回到此处方能执行。

3.参数取值: num(12

4.进入if语句条件为真(输出2(desolve(1) ,第二次递归调用,同样记住,只有第二次递归返回时才能执行write(‘ ‘)

5.参数取值: num(1

6.进入if语句条件为真(输出1(desolve( 0 ) ,第三次递归调用

7.参数取值: num(0

8.进入if语句条件为假,第三次调用结束,返回到第二次递归

9.执行write(‘ ‘);第二次递归结束,返回到第一次递归

10.执行write(‘ ‘);第一次递归结束,返回到主程序调用语句后继语句。

二、把具体问题写成递归的定义形式的方法是将重复的操作抽象出来

具体的例子,求a b两个整数的最大公约数。方法很多,以辗转相减,直到相等为例,方法是:把大数取大数减小数,直到相等。以a=14 b=18

我们抽象求解过程为gcd(a,b)

把过程中重复的部分抽象为以同样方法重做,但是a,b两个数不同。那么求解过程就简单地定义为:

(1)当a=b时,解为a,或b

(2)a≠b时,大数换为大数减小数,a,b为两新数,用同样方法重复gcd(a,b)

定义:gcd(a,b)为求a,b的最大公约数。

其中:min(a,b)为a ,b的小数。

Vb程序

Function private gcd( a,b :integer)

if a=b then return(a) else if a> b thenA=a-belse b= b-a

Return gcd(a, b)

End function

总结以上例子,可以看出,能写出递归的定义的条件是有结束递归的条件。

三、就是要用记忆化,以避免低效和溢出

递归的代码在运行时可能会运行效率极低,原因调用中有很多栈操作,,同时也会有可能出现栈溢出,导致程序终止运行。解决方法是记忆和模拟递归或非递归。以求斐波那契数列第N项为例

定义:feibo(n )

分析一下就知道,调用中一定有很多重复调用的地方,随着n值增大,重复的数量会急剧增多,运算的速度就可想而知了。解决方法就是利用记忆的方法,做法如下:

我们利用数组记忆:a(i)记录第i项,a(1)=0,a(2)=1

递归前检查a(n)是否已求,如果已求,就直接使用,不再递归,无值则递归。

Private Function feibo(n As Integer)

If n = 1 Thenfeibo = 0

If n = 2 Thenfeibo = 1

Else

If a(n - 1) > 0 Then

m = a(n - 1) + a(n - 2)

Else

If a(n - 2) > 0 Then

m = a(n - 2) + feibo(n - 1)

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文