第8讲B 递归函数.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,递归函数,2012/11/26,一种通过重复将问题分解为同类的子问题从而解决问题的方法,“The power of,recursion,evidently lies in the possibility of defining an infinite set of objects by a finite statement.In the same manner,an infinite number of computations can be described by a finite recursive program,even if this program contains no explicit repetitions.”,Niklaus Wirth,递归,阶乘,n!=n*(n-1)!,Fibonacci,数列,f(n)=f(n-1)+f(n-2),什么问题适合递归解决？,函数的递归调用,在调用一个函数的过程中又出现直接或间接,地调用该函数本身，称为函数的,递归调用,。,f2,函数,调用,f1,函数,函数的递归调用,f,函数,调用,f,函数,f1,函数,调用,f2,函数,直接调用本函数,间接调用本函数,函数的递归调用,例,7.6,有,5,个学生坐在一起,问第,5,个学生多少岁？他说比第,4,个学生大,2岁,问第,4,个学生岁数，他说比第,3,个学生大,2,岁,问第,3,个学生，又说比第,2,个学生大,2,岁,问第,2,个学生，说比第,1,个学生大,2,岁,最后问第,1,个学生，他说是,10,岁,请问第,5,个学生多大,函数的递归调用,解题思路：,要求第个年龄，就必须先知道第个年龄,要求第个年龄必须先知道第个年龄,第个年龄又取决于第个年龄,第个年龄取决于第个年龄,每个学生年龄都比其前个学生的年龄大,7.6,函数的递归调用,解题思路：,age(5)=age(4)+2,age(4)=age(3)+2,age(3)=age(2)+2,age(2)=age(1)+2,age(1)=10,age(5)age(4)+2,age(4),=age(3)+2,age(3),=age(2)+2,age(2),=age(1)+2,age(1),=10,age(2),=12,age(3),=14,age(4),=16,age(5),=18,递归边界,#include,int age(int n);,int main(),printf(NO.5,age:%dn,age,(5);,return 0;,int,age,(int n),int c;,if(n=1)c=10;,else c=,age,(n-1)+2;,return(c);,age(5),输出,age(5),main,c=age(4)+2,age,函数,n=5,c=age(3)+2,age,函数,n=4,c=age(1)+2,age,函数,n=2,c=age(2)+2,age,函数,n=3,c=10,age,函数,n=1,age(1)=10,age(2)=12,age(3)=14,age(4)=16,age(5)=18,18,例,7.7,用递归方法求！。,解题思路：,求！可以用递推方法,：,即从开始，乘，再乘一直乘到。,递推法的特点是从一个已知的事实,(,如,1!=1),出发，按一定规律推出下一个事实,(,如,2!=1!*2),，再从这个新的已知的事实出发，再向下推出一个新的事实,(3!=3*2!),。,n!=n*(n-1)!,。,例,7.7,用递归方法求！。,解题思路：,求！也可以用递归方法，即！等于！，而！，！,可用下面的递归公式表示：,#include,int fac(int n);,int main(),int n=0;,int y=0;,printf(input an integer number:);,scanf(%d,y=,fac,(n);,printf(%d!=%dn,n,y);,return 0;,int,fac,(int n),int f;,if(n0),printf(n%cn,x,y);,