第四章 递归算法.pptVIP

递归算法 递归程序设计是Pascal语言程序设计中的一种重要方法，它使许多复杂的问题变得简单，变得容易解决。递归算法的特点是：函数或过程调用它自己本身。其中直接调用自己称为直接递归；而把a调用b，b调用a的递归叫做间接递归。 例1 给定n（n≥1），用递归方法计算1+2+3+4+（n-1）+n。 program ex1; var s,t:integer; function fac(n:integer):integer; begin if n=1 then fac:=1 else fac:=fac(n-1)+n; end; begin read(t); s:=fac(t); writeln(s=,s); end. 例2 Hanoi汉诺塔问题 program ex2; var x,y,z:char; n,k:integer; procedure move(n:integer;a,c,b:char); begin if n=0 then exit else if n=1 then write(k,:from,a,--,c); move(n-1,a,c,b); inc(k); writeln(k,:from,a,--,c); move(n-1,b,a,c); end; begin write(n=);readln(n); k:=0;x:=a;y:=b;z:=c; move(n,x,y,z); end. * * 运行程序，当t=5时，输出结果：s=15，其递归调用执行过程是：（设t=3） 主程序 … s:=fac(3)； writeln(‘s=‘,s)； … … fac=1 n=1 fac(1)=1 ③ ④ … fac=fac(1)+2 n=1 fac(2)=3 ② ⑤ … fac=fac(2)+3 n=3 fac(3)=6 ① ⑥ 【算符分析】 本题可以用递归方法求解，其原因在于它符合递归的三个条件： 1、本题是累加问题：当前和等于前一次和加上当前项，并且前一次计算法与其相同。 2、给定的n是有限次的递归调用。 3、结束条件是当n=1时，s=1。 a b c a b c a b c a b c a b c a b c a b c a b c 一共做了2^n-1次 1、斐波拉切数列； 【问题描述】斐波拉切数列0、1、1、2、3、5、8….，从第三项起，每一项都是紧挨着前两项的和。写出计算斐波拉切数列任意一项的递归程序。（项数n，1=n=30） 【输入】10 【输出】34 2、倒序数； 【问题描述】用递归算法写程序，输入一个非负整数，输出这个数的倒序数。 【输入】123 【输出】321 上机练习 3、十进制数转换成八进制数； 【问题描述】用递归算法，把任意给定的十进制整数转换成八进制数输出。 【输入】15 【输出】17 4、求n！值； 【问题描述】用递归算法，求n！的精确值（n以一般整数输入） 【输入】10 【输出】10！=3628800 5、求最大公约数； 【问题描述】用递归方法求两个正整数m和n的最大公约数。（n500,m0）。 【输入】8 6 【输出】gcd=2 6、背包问题； 【问题描述】简单的背包问题。设有一个背包，可以放入的重量是s。现在有n件物品，重量分别为w1，w2，…wi（1=i=n)，均为正整数，从n件物品中挑选若干件，使得放入背包的重量之和正好为s。找一组解救就可以。 【输入】5 10 1 2 3 4 5 【输出】number：1 weight：1 number：4 weigth：4 number：5 wergth：5