《2022年递推与递归算法 .pdf》由会员分享，可在线阅读，更多相关《2022年递推与递归算法 .pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、递推与递归算法递推和递归是编程中常用的基本算法。在前面的解题中已经用到了这两种方法，下面对这两种算法基本应用进行详细研究讨论。一、递推递推算法是一种用若干步可重复的简单运算（规律）来描述复杂问题的方法。 例 1 植树节那天，有五位参加了植树活动，他们完成植树的棵数都不相同。问第一位同学植了多少棵时，他指着旁边的第二位同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；, 如此， 都说比另一位同学多植两棵。最后问到第五位同学时，他说自己植了10 棵。到底第一位同学植了多少棵树？解：设第一位同学植树的棵数为a1，欲求 a1，需从第五位同学植树的棵数a5 入手，根据“多两棵”这个规律
2、，按照一定顺序逐步进行推算：a5=10;a4=a5+2=12;a3=a4+2=14;a2=a3+2=16;a1=a2+2=18;Pascal 程序： Program Exam1 ; Var i, a: byte ; begin a: =10; 以第五位同学的棵数为递推的起始值 for i : =1 to 4 do 还有 4 人，递推计算4 次 a: = a+2 ; 递推运算规律 writeln( The Num is , a); readln end.本程序的递推运算可用如下图示描述：递推算法以初始起点 值为基础，用相同的运算规律，逐次重复运算，直至运算结束。这种从“起点”重复相同的方法直至到
3、达一定“边界”，犹如单向运动，用循环可以实现。递推的本质是按规律逐次推出（计算）下一步的结果。二、递归递归算法是把处理问题的方法定义成与原问题处理方法相同的过程，在处理问题的过程中又调用自身定义的函数或过程。仍用上例的计算植树棵数问题来说明递归算法：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 解：把原问题求第一位同学在植树棵数a1，转化为a1=a2+2; 即求 a2；而求 a2 又转化为 a2=a3+2; a3=a4+2 ;
4、 a4=a5+2; 逐层转化为求a2,a3,a4,a5且都采用与求a1 相同的方法；最后的 a5 为已知 , 则用 a5=10 返回到上一层并代入计算出a4；又用 a4 的值代入上一层去求a3; ., 如此 ,直到求出a1。因此：其中求 a x+1又采用求 ax 的方法。所以:定义一个处理问题的过程Num(x)：如果 X 1 ) X 3 = X * X 2 ( n 1 ), ( n 1 ) X n = X * X n-1 ( n 1 )因此将 X n转化为：其中求 X n -1又用求 X n的方法进行求解。定义过程xn(x , n: integer)求 X n; 如果 n 1 则递归调用xn
5、(x , n-1) 求 X n 1 ;当递归调用到达n=0，就执行t t :=1, 然后执行本“层”的后继语句;遇到过程的END就结束本次的调用，返回到上一“层”调用语句的地方，并执行其后续语句tt : =tt*x ;继续执行步骤，从调用中逐“层”返回，最后返回到主程序，输出tt的值。Pascal 程序： Program Exam2 ; Var tt, a, b: integer; Procedure xn(x, n: integer); 过程 xn(x, n)求 xn begin if n=0 then tt: =1 else begin xn(x, n-1) ; 递归调用过xn(x,n-1
6、)求 x n-1 tt: =tt*x end;end; begin write( input x, n: ); readln(a , b); 输入 a, b xn(a, b); 主程序调用过程xn(a, b)求 a b writeln(a, , b, = , tt) ; readln end .递归算法，常常是把解决原问题按顺序逐次调用同一“子程序”( 过程 ) 去处理，最后一次调用得到已知数据，执行完该次调用过程的处理，将结果带回，按“先进后出”原则，依次计算返回。如果处理问题的结果只需返回一个确定的计算值，可定义成递归函数。名师资料总结 - - -精品资料欢迎下载 - - - - - -
7、- - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 例 3 用递归函数求x!解：根据数学中的定义把求x! 定义为求x*(x-1)! ,其中求 (x-1) ! 仍采用求x! 的方法，需要定义一个求a！的过程或函数，逐级调用此过程或函数，即： (x-1)! = (x-1)*(x-2)! ; (x-2)! = (x-2)*(x-3)! ;直到 x=0 时给出 0! =1，才开始逐级返回并计算各值。定义递归函数：fac(a : integer): integer;如果 a=0，则 fac : =1;如果
8、a0，则调用函数fac : =fac(a-1)*a;返回主程序，打印fac(x)的结果。Pascal 程序： Program Exam3 ; Var x: integer; function fac(a: integer): integer;函数 fac(a) 求 a ! beginif a=0 then fac: =1 else fac: =fac(a-1)*a 函数 fac(a-1)递归求 (a-1) ! end; begin write( input x ); readln(x); writeln(x, ! = , fac(x); 主程序调用fac(x) 求 x ! readln end
9、.递归算法表现在处理问题的强大能力。然而，如同循环一样，递归也会带来无终止调用的可能性，因此，在设计递归过程（函数）时，必须考虑递归调用的终止问题，就是递归调用要受限于某一条件，而且要保证这个条件在一定情况下肯定能得到满足。 例 4 用递归算求自然数A，B的最大公约数。解：求最大公约数的方法有许多种，若用欧几里德发明的辗转相除方法如下：定义求X 除以 Y的余数的过程 ;如果余数不为0，则让 X=Y ， Y=余数，重复步骤，即调用过程;如果余数为0，则终止调用过程;输出此时的Y值。Pascal 程序： Program Exam4 ; Var a, b, d: integer; Procedure
10、 Gdd(x, y: nteger); 过程 begin if x mod y =0 then d : =y else Gdd(y, x mod y) 递归调用过程 end; begin write( input a, b= ) ; readln(a , b) ;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - Gdd(a, b) ; writeln( ( , a, , , b, )= , d ) ; readln end.简单地
11、说，递归算法的本质就是自己调用自己，用调用自己的方法去处理问题，可使解决问题变得简洁明了。按正常情况有几次调用，就有几次返回。但有些程序可以只进行递归处理，不一定要返回时才进行所需要的处理。 例 5 移梵塔。有三根柱A，B，C 在柱 A上有 N块盘片，所有盘片都是大的在下面，小片能放在大片上面。现要将 A上的 N 块片移到 C柱上， 每次只能移动一片，而且在同一根柱子上必须保持上面的盘片比下面的盘片小，请输出移动方法。解：先考虑简单情形。如果 N=3 ，则具体移动步骤为：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整
12、理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 假设把第3 步，第 4 步，第 6 步抽出来就相当于N=2的情况（把上面2 片捆在一起，视为一片）：所以可按“ N=2 ”的移动步骤设计：如果 N=0 ，则退出，即结束程序; 否则继续往下执行;用 C柱作为协助过渡， 将 A柱上的（N-1）片移到 B 柱上，调用过程 sub(n-1 , a, b, c) ;将 A柱上剩下的一片直接移到C柱上 ;用 A柱作为协助过渡，将B 柱上的（ N-1）移到 C 柱上，调用过程sub(n-1 , b, c, a) 。Pascal 程序： Program Exam65
13、; Var x, y, z : char;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - N, k : integer; Procedure sub(n: integer; a, c , b: char) ; begin if n=0 then exit; sub(n-1, a, b, c) ; inc(k); writeln(k, : from , a, - , c) ; sub(n-1, b, c, a); end; beg
14、in write( n= ; readln(n); k: =0; x: = A ; y: = B ; Z: = C ; sub(n, x, z, y) ; readln end .程序定义了把n 片从 A 柱移到 C 柱的过程sub(n,a,c,b)，这个过程把移动分为以下三步来进行：先调用过程sub(n-1 , a, b, c)，把 (n-1) 片从 A柱移到 B柱, C柱作为过渡柱 ;直接执行 writeln(a, - , c），把 A 柱上剩下的一片直接移到C柱上， ;调用 sub(n-1 , b, c, a)，把 B柱上的 (n-1) 片从 B移到 C柱上， A柱是过渡柱。对于 B柱上的 (n-1) 片如何移到， 仍然调用上述的三步。只是把 (n-1) 当成了 n， 每调用一次，要移到目标柱上的片数N就减少了一片，直至减少到n=0 时就退出，不再调用。exit是退出指令，执行该指令能在循环或递归调用过程中一下子全部退出来。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -