2023学年完整公开课版递归法

递归法递归算法

递归程序设计是Pascal语言程序设计中的一种重要方法，它使许多复杂的问题变得简单，变得容易解决。递归算法的特点是：函数或过程调用它自己本身。其中直接调用自己称为直接递归；而把a调用b，b调用a的递归叫做间接递归。例1给定n（n≥1），用递归方法计算1+2+3+4+（n-1）+n。【算符分析】

本题可以用递归方法求解，其原因在于它符合递归的三个条件：1、本题是累加问题：当前和等于前一次和加上当前项，并且前一次计算法与其相同。2、给定的n是有限次的递归调用。3、结束条件是当n=1时，s=1。programex1;vars,t:integer;functionfac(n:integer):integer;beginifn=1thenfac:=1elsefac:=fac(n-1)+n;end;beginread(t);s:=fac(t);writeln('s=',s);end.例1给定n（n≥1），用递归方法计算1+2+3+4+（n-1）+n。运行程序，当t=5时，输出结果：s=15，其递归调用执行过程是：（设t=3）主程序…s:=fac(3)；writeln(‘s=‘,s)；……fac=1n=1fac(1)=1③④…fac=fac(1)+2n=1fac(2)=3②⑤…fac=fac(2)+3n=3fac(3)=6①⑥例2Hanoi汉诺塔问题programex2;varx,y,z:char;n,k:integer;proceduremove(n:integer;a,c,b:char);beginifn=0thenexitelseifn=1thenwrite(k,':from',a,'-->',c);move(n-1,a,c,b);inc(k);writeln(k,':from',a,'-->',c);move(n-1,b,a,c);end;beginwrite('n=');readln(n);k:=0;x:='a';y:='b';z:='c';move(n,x,y,z);end.abcabcabcabcabcabcabcabc一共做了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的最大公约数。（n>500,m>0）。

【输入】86【输出】gcd=2上机练习6、背包问题；

【问题描述】简单的背包问题。设有一个背包，可以放入的重量是s。现在有n件物品，重量分别为w1，w2，…wi（1=<i<=n)，均为正整数，从n件物品中挑选若干件，使得放入背包的重量之和正好为s。找一组解救就可以。

【输入】51012345

【输出】number：1weight：1number：4weigth：4number：5wergth：5

上机练习7、2的幂次方；

【问题描述】任何一个正整数都可以用2的幂次方表示。例如：137=2^7+2^3+2^0同时约定用括号来表示方次，即a^b可以表示为a(b)。由此可知，137可以表示为：2(7)+2(3)+2(0)进一步：7=2^2+2+2^0;3=2+2^0所以最后127可以表示为：

2(2(