第9章_函数的高级应用

哈尔滨工业大学计算机科学与技术学院苏小红sxh,第9章函数的高级应用,C语言大学实用教程,本章内容,递归与递归函数指向函数的指针返回指针值的函数,递归问题的提出,“汉诺塔”（Hanoi）这是一个必须用递归方法才能解决的问题n=64时，18,446,744,073,709,551,615次1844亿亿次每次1微秒，需要60万年,递归问题的提出,AC，AB，CB，AC，BA，BC，AC,A,B,C,n=3,递归问题的提出,AC，AB，CB，AC，BA，BC，AC,A,B,C,递归问题的提出,AC，AB，CB，AC，BA，BC，AC,A,B,C,递归问题的提出,AC，AB，CB，AC，BA，BC，AC,A,B,C,递归问题的提出,AC，AB，CB，AC，BA，BC，AC,A,B,C,n更大些怎么办？,递归问题的提出,第一步：将问题简化。假设A杆上只有2个圆盘，即汉诺塔有2层，n2。,A,B,C,递归问题的提出,对于一个有n（n1）个圆盘的汉诺塔，将n个圆盘分为两部分：上面的n-1个圆盘和最下面的n号圆盘。将“上面的n-1个圆盘”看成一个整体。将n-1个盘子从一根木桩移到另一根木桩上将1个盘子从一根木桩移到另一根木桩上,A,C,B,递归问题的提出,将n个盘子从一根木桩移到另一根木桩上问题分解为：将n-1个盘子从一根木桩上移到另一根木桩上将1个盘子从一根木桩移到另一根木桩上设计一个函数，入口参数为n：将n个盘子从一根木桩移到另一根木桩上将n-1个盘子从一根木桩上移到另一根木桩上也要调用这个函数来实现出现了函数调用自己的问题递归调用（RecursiveCall）,递归（Recursion）函数,递归函数函数直接或间接调用自己直接调用方式：intf(x)inty,z;.z=f(x);,例9.1求整数n的阶乘n！,计算n！=n*(n-1)*(n-2)*1迭代法用递归的方法,例9.1求整数n的阶乘n！,#includemain()intn,i;longresult=1;printf(Inputn:);scanf(%d,迭代法,longfact(longn)longresult;if(n0)return1;elseif(n=0|n=1)/*递归终止条件*/return1;elsereturn(n*fact(n-1);/*递归调用*/,例9.1求整数n的阶乘n！,递归法,#includelongfact(longn);main()intn;longresult;printf(Inputn:);scanf(%d,例9.1求整数n的阶乘n！,递归法,递归调用过程,执行过程：fact(5)=5*fact(4)=120fact(4)=4*fact(3)=24fact(3)=3*fact(2)=6fact(2)=2*fact(1)=2fact(1)=1,main,fact(5),fact(4),fact(3),fact(2),fact(1),递归函数,递归方法的基本原理将复杂问题逐步化简，最终转化为一个最简单的问题最简单问题的解决，就意味着整个问题的解决递归调用应该能够在有限次数内终止递归递归调用如果不加以限制，将无数次的循环调用必须在函数内部加控制语句，只有当满足一定条件时，递归终止有时将其称为条件递归,递归函数,任何一个递归调用程序必须包括两部分递归循环继续的过程递归调用结束的过程if(递归终止条件成立)return递归公式的初值;elsereturn递归函数调用返回的结果值;,递归函数,思考：下面程序有什么问题阶乘函数的递归实现unsignedlongFac(unsignedintn)if(n0)printf(dataerror!);elseif(n=0|n=1)return1;elsereturnn*Fac(n-1);编译这个程序也会给出警告，提示“非所有控制分支都有返回值”。同时，运行程序后如果我们输入了一个负数，那么程序运行结果为：Inputa:-1Inputdataerror!a!=11,如果某个函数需要返回值的话，那么一定要确保该函数中的所有控制分支都有返回值。,递归函数,思考：下面程序有什么问题阶乘函数的递归实现unsignedlongFac(unsignedintn)if(n0)printf(dataerror!);elseif(n=0|n=1)return1;elsereturnn*Fac(n-1);存在死语句,存在另一个隐蔽的错误,返回指针值的函数,数据类型*函数名(参数表)例9.3:编一个函数连接两个字符串，然后返回连接后字符串的首地址,返回指针值的函数,char*MyStrcat(char*dstStr,char*srcStr)char*pStr=dstStr;while(*dstStr!=0)dstStr+;for(;*srcStr!=0;dstStr+,srcStr+)*dstStr=*srcStr;*dstStr=0;returnpStr;,返回指针值的函数,#include#defineARR_SIZE80char*MyStrcat(char*dstStr,char*srcStr);main()charfirstARR_SIZE=Hello;charsecondARR_SIZE=world;char*result=NULL;result=MyStrcat(first,second);printf(nTheresultis:%sn,result);,这个字符数组应该保证足够大,函数指针（FunctionPointers）,编译器将不带()的函数名解释为该程序的入口地址换句话说，函数名是指向程序入口的指针数据类型(*指针名)();例如：int(*p)();几个容易犯的错误：忘记了前一个()，写成int*p();声明一个返回值是整型指针的函数，函数名为p忘掉了后一个()，写成int(*p);定义了一个整型指针定义时后一个括号内参数类型与指向的函数不匹配,函数指针,求下列函数的定积分,函数指针,不用函数指针的编程方法floatIntegralFun1(floata,floatb)floats,h,y;intn,i;s=(1.0+a*a)+(1.0+b*b)/2.0;n=100;h=(b-a)/n;for(i=0;in;i+)y=a+i*h;s+=1.0+y*y;returns*h;,函数指针,不用函数指针的编程方法floatIntegralFun2(floata,floatb)floats,h,y;intn,i;s=(a/(1.0+a*a)+b/(1.0+b*b)/2.0;n=100;h=(b-a)/n;for(i=0;in;i+)y=a+i*h;s+=y/(1.0+y*y);returns*h;,函数指针,使用函数指针的编程方法floatIntegral(float(*f)(float),floata,floatb)floats,h,y;intn,i;s=(*f)(a)+(*f)(b)/2.0;n=100;h=(b-a)/n;for(i=0;ib;,函数指针,其他应用函数指针通常用在菜单驱动的系统中