1、第七章第1頁第1頁本章要點函數(shù)概念函數(shù)定義與調用函數(shù)遞歸調用數(shù)組作為函數(shù)參數(shù) 變量作用域函數(shù)作用域大連理工大學軟件學院第2頁第2頁main() 調用fa()fa()調用fb()fb()void fb( ) void fa( ) fb(); void main( ) fa(); 返回fa() 返回main() 7. 函數(shù)嵌套調用定義 申明 調用？大連理工大學軟件學院第3頁第3頁例1：輸入4個整數(shù)，找出其中最大數(shù)。用函數(shù)嵌套調用來處理。（遞推） 7. 函數(shù)嵌套調用#include void main() int max_4(int a,int b,int c,int d); / max_4函數(shù)申明

2、 int a,b,c,d,max; printf(Please enter 4 interger numbers:); scanf(%d %d %d %d ,&a,&b,&c,&d); max=max_4(a,b,c,d); /* 調用max_4函數(shù) */ printf(max=%d n,max); 大連理工大學軟件學院第4頁第4頁int max_4(int a,int b,int c,int d） int max_2(int,int);int m;m=max_2(a,b); m=max_2(m,c); m=max_2(m,d); return(m);int max_2(int a, int

3、b)if(ab) return a; else return b;運營情況下列：Please enter 4 interger numbers:11 45 54 0max=45大連理工大學軟件學院第5頁第5頁例2：定義一個求 bin(n,k)函數(shù)。分析： 定義函數(shù) fact ( m ) = m ! bin ( n , k ) = fact ( n ) / ( fact ( k ) * fact ( n - k ) ) 由主函數(shù)輸入數(shù)據 a 、 b ，求 bin ( a , b ) 7. 函數(shù)嵌套調用大連理工大學軟件學院第6頁第6頁#includelong fact ( int m ) int

4、i ; long sum = 1 ; for ( i = 1 ; i = m ; i+ ) sum *= i ; return sum ;long bin ( int n , int k ) return long ( fact ( n ) / ( fact ( k ) * fact ( n-k ) ) ) ; void main ( ) int a , b; long f1 , f2 ; scanf(“%d %d”, &a, &b) ; f1 = fact ( a ) / ( fact ( b ) * fact ( a-b ) ) ; f2 = bin ( a , b ) ;大連理工大學軟件

5、學院第7頁第7頁/函數(shù)嵌套調用示例求組合#includelong fact ( int m ) int i ; long sum = 1 ; for ( i = 1 ; i ）例4:遞歸求年齡大連理工大學軟件學院第24頁第24頁#include int age(int n)int c;if(n=1)c=10;elsec=age(n-1)+2;return c;void main()printf(%dn,age(5);運營結果下列：18 遞歸形式遞歸終止條件基本情況修改遞歸條件遞推法實現(xiàn)：void main()int i,sum=10;for(i=1;i=4;i+)sum=sum+2;print

6、f(%dn,sum);大連理工大學軟件學院第25頁第25頁int Factorial ( int n ) if ( n = = 0 ) return 1 ; else return n * Factorial ( n - 1 ) ;遞歸形式遞歸終止條件基本情況修改遞歸條件 7.6 函數(shù)遞歸調用 例5:遞歸求n階乘大連理工大學軟件學院第26頁第26頁int Factorial ( int n ) if ( n = = 0 ) return 1 ; else return n * Factorial ( n - 1 ) ;k3F (k)Output 3! = ?n3F (3)3* F (2)n2F

7、(2)2* F(1)n1F (0)1計算 Factorial (3) = 3!F(1)n01* F(0) 7.6 函數(shù)遞歸調用 大連理工大學軟件學院第27頁第27頁k3F (3)Output 3! = ?n3F (3)3* F (2)n2F(2)2* F(1)n1F (0)1F(1)n01* F(0)1計算 Factorial (3) = 3!int Factorial ( int n ) if ( n = = 0 ) return 1 ; else return n * Factorial ( n - 1 ) ; 7.6 函數(shù)遞歸調用 大連理工大學軟件學院第28頁第28頁k3F (3)Out

8、put 3! = ?n3F (3)3* F (2)n2F(2)2* F(1)n1F(1)計算 Factorial (3) = 3!F (1) = 11int Factorial ( int n ) if ( n = = 0 ) return 1 ; else return n * Factorial ( n - 1 ) ; 7.6 函數(shù)遞歸調用 大連理工大學軟件學院第29頁第29頁k3F (3)Output 3! = ?n3F (3)3* F (2)n2F(2)F(2) = 22計算 Factorial (3) = 3!int Factorial ( int n ) if ( n = = 0

9、) return 1 ; else return n * Factorial ( n - 1 ) ; 7.6 函數(shù)遞歸調用 大連理工大學軟件學院第30頁第30頁k3F (3)Output 3! = ?n3F (3)F(3) = 6計算 Factorial (3) = 3!int Factorial ( int n ) if ( n = = 0 ) return 1 ; else return n * Factorial ( n - 1 ) ; 7.6 函數(shù)遞歸調用 大連理工大學軟件學院第31頁第31頁k3F (3)Output 3! = 63! = 6計算 Factorial (3) = 3!

10、int Factorial ( int n ) if ( n = = 0 ) return 1 ; else return n * Factorial ( n - 1 ) ; 7.6 函數(shù)遞歸調用 大連理工大學軟件學院第32頁第32頁k3F (3)k3F (3)n3F (3)3* F (2)n2F(2)2* F(1)n1F (0)1F(1)n01* F(0)F (1) = 1F(2) = 2F(3) = 6Output 3! = 6計算 Factorial (3) = 3!int Factorial ( int n ) if ( n = = 0 ) return 1 ; else return

11、 n * Factorial ( n - 1 ) ; 7.6 函數(shù)遞歸調用 大連理工大學軟件學院第33頁第33頁int Fibonacci ( int n ) if ( n = 2 ) return 1 ; else return Fibonacci ( n-1 ) + Fibonacci ( n-2 ) ; 7.6 函數(shù)遞歸調用 例6:遞歸求斐波那契數(shù)列遞歸形式遞歸終止條件基本情況修改遞歸條件遞歸形式修改遞歸條件大連理工大學軟件學院第34頁第34頁int Fibonacci ( int n ) if ( n = 2 ) return 1 ; else return Fibonacci ( n

12、-1 ) + Fibonacci ( n-2 ) ; Fibonacci (5)Fibonacci (4)Fibonacci (3)Fibonacci (3)Fibonacci (2)Fibonacci (2)Fibonacci (1)大連理工大學軟件學院第35頁第35頁Fibonacci (5)Fibonacci (4)Fibonacci (3)Fibonacci (3)Fibonacci (2)Fibonacci (2)Fibonacci (1)11+2int Fibonacci ( int n ) if ( n = 2 ) return 1 ; else return Fibonacci

13、 ( n-1 ) + Fibonacci ( n-2 ) ; 大連理工大學軟件學院第36頁第36頁Fibonacci (5)Fibonacci (4)Fibonacci (3)2Fibonacci (3)Fibonacci (2)13int Fibonacci ( int n ) if ( n = 2 ) return 1 ; else return Fibonacci ( n-1 ) + Fibonacci ( n-2 ) ; 大連理工大學軟件學院第37頁第37頁Fibonacci (5)Fibonacci (3)3Fibonacci (3)Fibonacci (1)Fibonacci (2

14、)112int Fibonacci ( int n ) if ( n = 2 ) return 1 ; else return Fibonacci ( n-1 ) + Fibonacci ( n-2 ) ; 大連理工大學軟件學院第38頁第38頁Fibonacci (5)Fibonacci (4)Fibonacci (3)Fibonacci (3)Fibonacci (2)Fibonacci (1)Fibonacci (2)Fibonacci (2)Fibonacci (1)532211111int Fibonacci ( int n ) if ( n = 2 ) return 1 ; else

15、 return Fibonacci ( n-1 ) + Fibonacci ( n-2 ) ; 大連理工大學軟件學院第39頁第39頁 7.6 函數(shù)遞歸調用 遞推：知道第一個，推出下一個，直到到達目的。 遞歸：要知道第一個，需要先知道下一個，直到一個已知 ，再反回來，得到上一個，直到第一個。遞推：從已知到未知，從簡樸到復雜。遞歸：從未知到已知，從復雜到簡樸。遞推：直接自下向頂運算，由f(1)算到f(n)。 遞歸：自頂向下逐步拓展需求，最后自下向頂運算。即由f(n) 拓展到f(1)，再由f(1)逐步算回f(n)。遞歸：在函數(shù)內調用函數(shù)本身。遞推：往往通過循環(huán)迭代求值。遞歸與遞推（迭代）比較大連理工

16、大學軟件學院第40頁第40頁遞歸與非遞歸比較遞歸目的是簡化程序設計，使程序易讀；遞歸增長了系統(tǒng)開銷，延長了CPU執(zhí)行時間，多占用了內存?？臻g；非遞歸效率高，但是程序可讀性差；遞歸與非遞歸選擇大多數(shù)遞歸函數(shù)都能用非遞歸函數(shù)來代替。能用遞推就用遞推,普通情況比遞歸快,除非有問題不用遞歸做不出來。 7.6 函數(shù)遞歸調用 大連理工大學軟件學院第41頁第41頁遞歸法/ n! recursive functionint Factorial ( int n ) if ( n = = 0 ) return 1 ; return n * Factorial ( n - 1 ) ;long fact ( int

17、m ) int i ; long sum = 1 ; for ( i = 1 ; i n時，m 與 n 最大公約數(shù)等于 n 和 m%n 最大公約數(shù)；當 n = 0時，m 和 n 最大公約數(shù)等于 m 。求最大公約數(shù) 7.6 函數(shù)遞歸調用 大連理工大學軟件學院第43頁第43頁 /迭代法long g2(int a, int b) int t;while(b!=0)t=a%b;a=b;b=t;return a;/遞歸法long g1(int a, int b) if(a%b=0) return b; return g1(b, a%b); 求最大公約數(shù) 7.6 函數(shù)遞歸調用 大連理工大學軟件學院第44頁

18、第44頁7.7 數(shù)組作為函數(shù)參數(shù) 數(shù)組元素和數(shù)組名都能夠作為參數(shù)傳遞給函數(shù)數(shù)組元素作參數(shù)，按值傳遞方式傳遞給函數(shù)；數(shù)組名作參數(shù)，常按地址方式傳遞給函數(shù)。 數(shù)組名用于傳遞地址（即數(shù)組第一個元素地址）； 把數(shù)組名作為參數(shù)傳遞到函數(shù)中，實參和形參共用同一段內存空間，可通過改變形參而改變實參。大連理工大學軟件學院第45頁第45頁一、數(shù)組元素作參數(shù)（性質與簡樸變量相同，值傳遞）#includevoid fun( int, int, int );void main( ) int i , a3 = 1, 2, 3 ; fun ( a0 , a1 , a2 ) ; for ( i = 0 ; i 3 ; i

19、+ ) printf(“%5d”, a i );void fun ( int a, int b, int c ) a+ ; b+ ; c+ ; printf(“%5d %5d %5d n”, a , b ,c) ;修改局部量傳值參數(shù)7.7 數(shù)組作為函數(shù)參數(shù)大連理工大學軟件學院第46頁第46頁a 0 x0065FDD012345678910 pan0065FDD00i0m10二、數(shù)組名作參數(shù)（傳遞地址）#include int sum ( int pa , int n ) int m = 0 , i ; for ( i = 0 ; i n ; i + ) m += pa i ; return m;void main(