1、第七章第1頁第1頁本章要點(diǎn)函數(shù)概念函數(shù)定義與調(diào)用函數(shù)遞歸調(diào)用數(shù)組作為函數(shù)參數(shù) 變量作用域函數(shù)作用域大連理工大學(xué)軟件學(xué)院第2頁第2頁main() 調(diào)用fa()fa()調(diào)用fb()fb()void fb( ) void fa( ) fb(); void main( ) fa(); 返回fa() 返回main() 7. 函數(shù)嵌套調(diào)用定義 申明 調(diào)用？大連理工大學(xué)軟件學(xué)院第3頁第3頁例1：輸入4個(gè)整數(shù)，找出其中最大數(shù)。用函數(shù)嵌套調(diào)用來處理。（遞推） 7. 函數(shù)嵌套調(diào)用#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); /* 調(diào)用max_4函數(shù) */ printf(max=%d n,max); 大連理工大學(xué)軟件學(xué)院第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;運(yùn)營情況下列：Please enter 4 interger numbers:11 45 54 0max=45大連理工大學(xué)軟件學(xué)院第5頁第5頁例2：定義一個(gè)求 bin(n,k)函數(shù)。分析： 定義函數(shù) fact ( m ) = m ! bin ( n , k ) = fact ( n ) / ( fact ( k ) * fact ( n - k ) ) 由主函數(shù)輸入數(shù)據(jù) a 、 b ，求 bin ( a , b ) 7. 函數(shù)嵌套調(diào)用大連理工大學(xué)軟件學(xué)院第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 ) ;大連理工大學(xué)軟件

5、學(xué)院第7頁第7頁/函數(shù)嵌套調(diào)用示例求組合#includelong fact ( int m ) int i ; long sum = 1 ; for ( i = 1 ; i ）例4:遞歸求年齡大連理工大學(xué)軟件學(xué)院第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);運(yùn)營結(jié)果下列：18 遞歸形式遞歸終止條件基本情況修改遞歸條件遞推法實(shí)現(xiàn)：void main()int i,sum=10;for(i=1;i=4;i+)sum=sum+2;print

6、f(%dn,sum);大連理工大學(xué)軟件學(xué)院第25頁第25頁int Factorial ( int n ) if ( n = = 0 ) return 1 ; else return n * Factorial ( n - 1 ) ;遞歸形式遞歸終止條件基本情況修改遞歸條件 7.6 函數(shù)遞歸調(diào)用 例5:遞歸求n階乘大連理工大學(xué)軟件學(xué)院第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計(jì)算 Factorial (3) = 3!F(1)n01* F(0) 7.6 函數(shù)遞歸調(diào)用 大連理工大學(xué)軟件學(xué)院第27頁第27頁k3F (3)Output 3! = ?n3F (3)3* F (2)n2F(2)2* F(1)n1F (0)1F(1)n01* F(0)1計(jì)算 Factorial (3) = 3!int Factorial ( int n ) if ( n = = 0 ) return 1 ; else return n * Factorial ( n - 1 ) ; 7.6 函數(shù)遞歸調(diào)用 大連理工大學(xué)軟件學(xué)院第28頁第28頁k3F (3)Out

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

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

10、int Factorial ( int n ) if ( n = = 0 ) return 1 ; else return n * Factorial ( n - 1 ) ; 7.6 函數(shù)遞歸調(diào)用 大連理工大學(xué)軟件學(xué)院第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計(jì)算 Factorial (3) = 3!int Factorial ( int n ) if ( n = = 0 ) return 1 ; else return

11、 n * Factorial ( n - 1 ) ; 7.6 函數(shù)遞歸調(diào)用 大連理工大學(xué)軟件學(xué)院第33頁第33頁int Fibonacci ( int n ) if ( n = 2 ) return 1 ; else return Fibonacci ( n-1 ) + Fibonacci ( n-2 ) ; 7.6 函數(shù)遞歸調(diào)用 例6:遞歸求斐波那契數(shù)列遞歸形式遞歸終止條件基本情況修改遞歸條件遞歸形式修改遞歸條件大連理工大學(xué)軟件學(xué)院第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)大連理工大學(xué)軟件學(xué)院第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 ) ; 大連理工大學(xué)軟件學(xué)院第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 ) ; 大連理工大學(xué)軟件學(xué)院第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 ) ; 大連理工大學(xué)軟件學(xué)院第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 ) ; 大連理工大學(xué)軟件學(xué)院第39頁第39頁 7.6 函數(shù)遞歸調(diào)用 遞推：知道第一個(gè)，推出下一個(gè)，直到到達(dá)目的。 遞歸：要知道第一個(gè)，需要先知道下一個(gè)，直到一個(gè)已知 ，再反回來，得到上一個(gè)，直到第一個(gè)。遞推：從已知到未知，從簡樸到復(fù)雜。遞歸：從未知到已知，從復(fù)雜到簡樸。遞推：直接自下向頂運(yùn)算，由f(1)算到f(n)。 遞歸：自頂向下逐步拓展需求，最后自下向頂運(yùn)算。即由f(n) 拓展到f(1)，再由f(1)逐步算回f(n)。遞歸：在函數(shù)內(nèi)調(diào)用函數(shù)本身。遞推：往往通過循環(huán)迭代求值。遞歸與遞推（迭代）比較大連理工

16、大學(xué)軟件學(xué)院第40頁第40頁遞歸與非遞歸比較遞歸目的是簡化程序設(shè)計(jì)，使程序易讀；遞歸增長了系統(tǒng)開銷，延長了CPU執(zhí)行時(shí)間，多占用了內(nèi)存棧空間；非遞歸效率高，但是程序可讀性差；遞歸與非遞歸選擇大多數(shù)遞歸函數(shù)都能用非遞歸函數(shù)來代替。能用遞推就用遞推,普通情況比遞歸快,除非有問題不用遞歸做不出來。 7.6 函數(shù)遞歸調(diào)用 大連理工大學(xué)軟件學(xué)院第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時(shí)，m 與 n 最大公約數(shù)等于 n 和 m%n 最大公約數(shù)；當(dāng) n = 0時(shí)，m 和 n 最大公約數(shù)等于 m 。求最大公約數(shù) 7.6 函數(shù)遞歸調(diào)用 大連理工大學(xué)軟件學(xué)院第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ù)遞歸調(diào)用 大連理工大學(xué)軟件學(xué)院第44頁

18、第44頁7.7 數(shù)組作為函數(shù)參數(shù) 數(shù)組元素和數(shù)組名都能夠作為參數(shù)傳遞給函數(shù)數(shù)組元素作參數(shù)，按值傳遞方式傳遞給函數(shù)；數(shù)組名作參數(shù)，常按地址方式傳遞給函數(shù)。 數(shù)組名用于傳遞地址（即數(shù)組第一個(gè)元素地址）； 把數(shù)組名作為參數(shù)傳遞到函數(shù)中，實(shí)參和形參共用同一段內(nèi)存空間，可通過改變形參而改變實(shí)參。大連理工大學(xué)軟件學(xué)院第45頁第45頁一、數(shù)組元素作參數(shù)（性質(zhì)與簡樸變量相同，值傳遞）#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ù)大連理工大學(xué)軟件學(xué)院第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(