第5章函数20141120.pptVIP

main() fact(3) fact(2) fact(1) { .... { .... { .... { .... printf(fact(3)); f=3*fact(2); f=2*fact(1); f=1; } return(f); return(f) ; return(f); } } } fact(3)= 3*fact(2)＝ 2*fact(1)＝ fact(1)＝1 2*1=2 3*2=6 递归函数 fact( n )的实现过程 关于递归函数的总结 递归调用应该能够在有限次数内终止递归 递归调用若不加以限制，将无限循环调用 必须在函数内部加控制语句，仅当满足一定条件时，递归终止，称为条件递归 任何一个递归调用程序必须包括两部分 递归循环继续的过程 递归调用结束的过程 if (递归终止条件成立) return 递归公式的初值; else return 递归函数调用返回的结果值; 5.6.2 最大公约数 编程计算两个整数的最大公约数。 两个整数的最大公约数是能够整除这两个整数的最大整数。求最大公约数的最经典算法是欧几里德算法又称辗转相除法。 用gcd(a, b)表示两个数的最大公约数。则： （1）若a÷b的余数r不为0，?则gcd(a, b)?=?gcd(b, r)； （2）a?和a的倍数之最大公约数为?a。 举例： gcd(468, 45) (余数r = 18) =gcd(45, 18) (余数r = 9) =gcd(18, 9） (余数r = 0) =9 最大公约数的递归函数 递归函数gcd(a, b) gcd(a, b) = b， 如果a是b的倍数； gcd(a, b) = gcd(b, a%b) ， 如果a不是b的倍数。 int gcd(int a, int b) { int r = a % b; if( r == 0) return b; //直接求解 else return gcd(b, r); //递归求解 } 课堂练习：逆序输出n个整数 输入n个整数，然后逆序输出这n个整数。例如： 输入 ： 5 11 22 33 44 55 输出：55 44 33 22 11 递归函数实现： void inverse( int n) { if(n == 0) return; //直接求解 读入一个整数number; 调用自身, 读入n-1个整数并逆序输出 //递归求解 输出number; } 模仿练习：顺序输出各位数字 输入一个正整数n，然后顺序输出n的各位数字，用空格隔开。例如： 输入 ： 4567 输出：4 5 6 7 递归函数实现： void inverse( int n) { if(n == 0) return; //直接求解 读入一个整数number; 调用自身, 读入n-1个整数并逆序输出 //递归求解 输出number; } 5.6.3 最近共同祖先 如图所示，由正整数1,2,3，...组成了一颗无限大的二叉树。从某一个结点到根结点（编号是1）都有一条唯一的路径。对于两个结点x和y，在它们到根的路径上所经过的共同的结点称为x和y的共同祖先，而其中距离x和y最近的结点，称为最近共同祖先。 给定x和y，求x和y的最近共同祖先。 解题思路 从图中我们可以看出孩子和双亲之间的关系，如果双亲编号为i，则左孩子编号为2*i，右孩子编号为2*i+1。反之，对于一个编号为i的结点，它的双亲的编号为[i/2]。所以，如果要求两个结点x和y的共同祖先，可以从编号之间的关系来判断。 if(x == y)