第3讲函数的递归调用

第3讲函数的递归调用本讲内容：

(1)递归函数的定义与调用

(2)

汉诺塔问题

(3)分治法的基本思想

(4)二分搜索技术

递归的概念递归函数:直接调用自己或通过另一函数间接调用自己的函数用递归求解问题的特点(1)存在递归的终止条件(2)存在导致问题求解的递归方式1n=0,1n*(n-1)!n>0

n!=递归的终止条件递归公式例:用递归的方法求n!1n=0,1n*(n-1)!n>1

n!=递归的终止条件递归方式4!=4*(4-1)!

返回值6返回值2返回值13!=3*(3-1)!2!=2*(2-1)!1!=1主调函数返回值24调用#include<stdio.h>floatfac(intn);voidmain(){intm;floaty;

scanf(“%d”,&m);

y=fac(m);/*调用函数fac()*/

printf(“%d!=%15.0f\n”,m,y);}函数声明递归调用函数定义floatfac(intn){floatf;if(n<0){printf(“error!”);f=-1;}elseif(n==0||n==1)f=1;elsef=n*fac(n-1);/*递归调用自己*/return(f);}main函数输入m③y=fac(m)输出y⑥调用facmn③

因

3!=0,1f=3*fac(3-1)返回f⑥调用facmn②返回f②返回f①

因

2!=0,1f=2*fac(2-1)调用facmn①因1==1f=1结束递归调用过程:递归法求Fibonacci数列Fibonacci数列:1,1,2,3,5,8,13…迭代法求Fibonacci数列的前20项#include<stdio.h>voidmain(){inti,f1=1,f2=1,f3;printf(“%8d%8d”,f1,f2);

for(i=3;i<=20;i++){f3=f1+f2;f1=f2;f2=f3;printf(“%8d”,f3);

if(i%4==0)putchar(‘\n’);}

}迭代法在已知数列前2项的基础上,从第3项开始,依次向后计算,得出数列的每一项思考:怎样用递归的方法求解？定义Fibonacci数列的递归数学模型：递归法求Fibonacci数列1n=0,1F(n-1)+F(n-2)n>1

F(n)=递归的终止条件递归公式int

Fib(intn){if(n<0){printf(“error!”);exit(-1);}else

if(n<=1)return1;elsereturnFib(n-1)+Fib(n-2);}递归法求Fibonacci数列用递归法求Fibonacci数列Fib(4)return+Fib(3)Fib(2)return+Fib(1)Fib(0)return+Fib(2)Fib(1)return+Fib(1)Fib(0)return1return1return1return1return1递归法是从第n项开始向前计算,当n等于0或1时结束递归调用,开始返回112111235n=20时,要进行21891次递归调用思考:求Fibonacci数列的迭代法和递归法谁好？递归法求Fibonacci数列一个黄铜板上，插着三根宝石针，其中一根针上从下到上放了由大到小的64块金片，这就是Hanoi塔。Hanoi塔问题：就是如何将64块金片按照梵天不渝法则，由一根宝石针全部移动到另一根宝石针上去。Hanoi问题Hanoi问题问题描述：设A,B,C是3个塔座。在塔座A上有n个圆盘,这些圆盘自下而上,由大到小的叠放。要求将A上的圆盘移到C上,并仍按同样顺序叠放。移动圆盘应遵守以下规则：规则1：每次只能移动1个圆盘规则2：任何时刻都不允许将大圆盘压在小圆盘之上规则3：在满足规则1和2的前提下,可将圆盘移至任一塔座上ABC3个圆盘的移动过程演示A→CA→BHanoi问题ABC3个圆盘的移动过程演示C→BHanoi问题ABC3个圆盘的移动过程演示A→CHanoi问题ABC3个圆盘的移动过程演示B→AB→CHanoi问题ABCn较大时怎么办？3个圆盘的移动过程演示A→Cn个圆盘需要2n-1次移动n=64时,需要264-1

次移动，即1844亿亿次移动。若每次移动需用1微秒,则总共需要60万年时间！3个圆盘一共需要7次移动：A→C，A→B，C→B，A→C，B→A，B→C，A→CHanoi问题移动步骤：①(n-1)个圆盘AB②第n个圆盘AC③(n-1)个圆盘BCACBn个圆盘的移动方法：n个圆盘分为2部分上面(n-1)个圆盘最下面的第n号圆盘(n-1)个圆盘怎么移动？递归何时结束？Hanoi问题第n个圆盘ACn=1(n-1)个圆盘AB第n个圆盘AC(n-1)个圆盘BCn>1voidHan(intn,intA,intB,intC){if(n==1)Move(n,A,C);else{Han(n-1,A,C,B);Move(n,A,C);Han(n-1,B,A,C);}}递归法求解hanoi问题//将n-1个盘子从A移到B,借助于C//将n-1个盘子从B移到C,借助于A//将第n个盘子从A移到C//将n个盘子从A移到C,借助于B//将1个盘子从A移到C请特别注意这3个参数的顺序Hanoi问题Han(3,A,B,C){if(n==1)

Move(n,A,C);else{

Han(2,A,C,B);

Move(3,A,C);

Han(2,B,A,C);

}}Han(2,A,C,B){if(n==1)Move(n,A,B);else{

Han(1,A,B,C);

Move(2,A,B);Han(1,C,A,B);

}}Han(1,A,B,C){if(n==1)

Move(1,A,C);}Han(1,C,A,B){if(n==1)

Move(1,C,B);}Han(2,B,A,C){if(n==1)Move(n,B,C);else{

Han(1,B,C,A);

Move(2,B,C);Han(1,A,B,C);

}}Han(1,B,C,A){if(n==1)

Move(1,B,A);}Han(1,A,B,C){if(n==1)

Move(1,A,C);}

ABC

ABC

ABC

ABC

ABC

ABC

ABC

ABC递归与迭代递归与迭代都涉及循环迭代是显示使用循环结构递归通过重复调用函数实现循环递归与迭代都涉及终止测试迭代在循环条件为假时终止递归在满足终止条件时结束递归与迭代都可以无限进行迭代当循环条件永真时形成无限循环递归如果无法到达终止条件则发生无穷递归递归与迭代有些问题既可用迭代法求解，也可用递归法求解如：求n！，Fibonacci数列，求xn

等迭代法编程代码相对比较复杂，但运行效率高递归法编程结构清晰，可读性强，代码简洁明了，但运行效率很低递归和迭代的优缺点有的问题只能用递归法求解，如：汉诺塔问题(n较大时)递归法优于迭代法之处在于它能更自然的反映问题另外选择递归的一个原因是可能没有明显的迭代方案课后作业课本P202：8.13，8.17分治法的基本思想分治法的思想:分而治之。将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同，(如果子问题的规模仍然不够小，则再划分为k个子问题),然后递归的求解这些子问题，最后用适当的方法将各子问题的解合并成原问题的解。原问题(规模为n)子问题1子问题2子问题k…子问题1子问题2子问题k…相同类型合并解子问题1子问题2子问题k…子问题1子问题2子问题k…分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题该问题所分解出的各个子问题是相互独立的利用分解出的子问题的解可以合并为该问题的解分治法的基本思想前提条件：有一组数已经按从小到大(或从大到小)排序目标：输入一个数x，在这组数查找是否有x二分搜索的步骤：1、确定三个关键下标的初值：bott=0,top=8,

mid=(bott+top)/2;2、判断要找的数x是否等于a[mid]①x==a[mid]找到，结束x<a[mid]在a[bott]—a[mid-1]之间继续查找x

top=mid-1;mid=(bott+top)/2;③x>a[mid]在a[mid+1]—a[top]之间继续查找x

bott=mid+1;mid=(bott+top)/2;-15-6079235482101midbotttopa[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]二分搜索算法二分搜索实例:设在数组a中顺序放了以下9个元素：检索x=9,

9==a[4],一次比较就成功,

最好情况-15-6079235482101a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]①②③③④②③④检索x=-15,-15<a[4],-15<a[1],

-15==a[0],

3次比较,

成功检索x=101,101>a[4],101>a[6],101>a[7],

101==a[8],

4次比较,

成功检索x=8,8<a[4],8>a[1],8>a[2],8>a[3],4次比较,

不成功二分搜索算法#include<stdio.h>#defineN10int

find(inta[],intx,int

bott,inttop)；voidmain(){inti,x,a[N],result;

printf("\n

输入数组a:\n");for(i=0;i<N;i++)scanf("%d",&a[i]);

printf(“输入要查找的数