[递归在编程中的妙用] 进制转换器

　　 [摘要] 在子程序内直接或间接调用了它本身,就叫做递归调用,简称递归。要理解递归,必须用程序跟踪的方法,执行每一步、理解每一步,你会理解递归的过程。 　　[关键词] 调用 递归 记忆化
　　
　　笔者在近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浏览器用户请先下载安装 原版全文