函數(shù)的遞歸調(diào)用

1、L/O/G/O6.6 6.6 函數(shù)的遞歸調(diào)用函數(shù)的遞歸調(diào)用章節(jié)回顧章節(jié)回顧1. 以下正確的函數(shù)定義形式為：以下正確的函數(shù)定義形式為：【 】Adouble fun(int x,int y) B. double fun(int x ;int y)C. double fun(int x,int y) ; D. double fun(int x,y)2. 以下不正確的描述是：以下不正確的描述是：【 】A在在C程序中，實(shí)參可以是常量、變量或表達(dá)式程序中，實(shí)參可以是常量、變量或表達(dá)式B在在C程序中，形參可以是常量、變量或表達(dá)式程序中，形參可以是常量、變量或表達(dá)式C在在C程序中，實(shí)參可以是任意類型程序中，實(shí)

2、參可以是任意類型D形參應(yīng)與其對(duì)應(yīng)的實(shí)參在個(gè)數(shù)、類型、順序上保持一致形參應(yīng)與其對(duì)應(yīng)的實(shí)參在個(gè)數(shù)、類型、順序上保持一致3. 在在C程序中，用簡(jiǎn)單變量作為實(shí)參時(shí)，它與對(duì)應(yīng)的形參之間的數(shù)據(jù)傳遞方程序中，用簡(jiǎn)單變量作為實(shí)參時(shí)，它與對(duì)應(yīng)的形參之間的數(shù)據(jù)傳遞方式為：式為：【 】A 地址傳遞地址傳遞 B 單向傳遞單向傳遞 C 按用戶指定方式傳遞按用戶指定方式傳遞 D 由實(shí)參傳遞給形參，再由形參傳回給實(shí)參由實(shí)參傳遞給形參，再由形參傳回給實(shí)參4. 在在C程序中，函數(shù)的返回值的類型由：程序中，函數(shù)的返回值的類型由：【 】Areturn語(yǔ)句中的表達(dá)式的類型決定語(yǔ)句中的表達(dá)式的類型決定B調(diào)用該函數(shù)時(shí)的調(diào)用函數(shù)決定調(diào)用該

3、函數(shù)時(shí)的調(diào)用函數(shù)決定C調(diào)用該函數(shù)時(shí)由系統(tǒng)臨時(shí)決定調(diào)用該函數(shù)時(shí)由系統(tǒng)臨時(shí)決定D在定義該函數(shù)時(shí)由函數(shù)的類型決定在定義該函數(shù)時(shí)由函數(shù)的類型決定ABBD主要內(nèi)容主要內(nèi)容一、一、 引入新問(wèn)題引入新問(wèn)題 二、二、 函數(shù)遞歸概述函數(shù)遞歸概述 三、三、 漢諾塔問(wèn)題漢諾塔問(wèn)題 四、四、 課堂練習(xí)課堂練習(xí) 五、五、 課程小結(jié)課程小結(jié) 一、引入新問(wèn)題一、引入新問(wèn)題 五位學(xué)生坐成一排，學(xué)生之間不知道相互的年齡。老師問(wèn)最后一名學(xué)生，即第5名學(xué)生，她和她前面這一排學(xué)生的年齡總和是多少？思考問(wèn)題：12345你們年齡之和？你們年齡之和？你們年齡之和？你們年齡之和？你們年齡之和？你們年齡之和？你們年齡之和？你們年齡之和？我們共

4、我們共3737歲歲（27+1027+10）我們共我們共2727歲歲（19+819+8）我們共我們共1919歲歲（10+910+9）我我1010歲歲你們年齡之和你們年齡之和我們共我們共4646歲歲（37+937+9）) 1() 1() 1()(nmyAgenntotalAgemyAgentotalAge遞歸公式遞歸公式二、函數(shù)遞歸概述二、函數(shù)遞歸概述1. 遞歸的定義： 調(diào)用一個(gè)函數(shù)時(shí)直接或間接調(diào)用自身, 稱之為函數(shù)的遞歸函數(shù)的遞歸。2. 一個(gè)問(wèn)題能夠成為遞歸必須具備的條件是：3. 程序中的遞歸方式:直接遞歸調(diào)用：直接遞歸調(diào)用：函數(shù)直接調(diào)用本身間接遞歸調(diào)用：間接遞歸調(diào)用：函數(shù)間接調(diào)用本身 后一部分

5、與原始問(wèn)題類似后一部分與原始問(wèn)題類似 后一部分是原始問(wèn)題的簡(jiǎn)化后一部分是原始問(wèn)題的簡(jiǎn)化) 1() 1() 1()(nmyAgenntotalAgemyAgentotalAge 說(shuō)明說(shuō)明C C語(yǔ)言語(yǔ)言對(duì)遞歸函數(shù)的自調(diào)用次數(shù)沒(méi)有限制對(duì)遞歸函數(shù)的自調(diào)用次數(shù)沒(méi)有限制必須有遞歸結(jié)束條件必須有遞歸結(jié)束條件 int f(x) int x ; int y, z ; z =f(y) ; return(2*z) ; int f1(x)int x ; int y, z ; z =f2(y) ; return(2*z) ; int f2(t)int t ; int a, c ; c =f1(a) ; return(3

6、+c) ; 用用C C語(yǔ)言解決上述思考題語(yǔ)言解決上述思考題9歲歲8歲歲10歲歲9歲歲totalAge(5)=myAge+totalAge(4)totalAge(4)=myAge+totalAge(3)totalAge(3)=myAge+totalAge(2)totalAge(2)=myAge+totalAge(1)totalAge(4)=10+27=37totalAge(3)=8+19=27totalAge(2)=9+10=19totalAge(1)=myAge=10Main()Main()調(diào)用子函數(shù)調(diào)用子函數(shù)totalAge(5)=9+37=4610歲歲) 1() 1() 1()(nmyAg

7、enntotalAgemyAgentotalAgetotalAge(1)=myAgevoid main() int m; printf(input the students number:); scanf(%d,&m); if(m1) total=myAge+totalAge(n-1); else if(n=1) total=myAge; printf(from totalnumber(%d)return %dn,n,total); getch(); return total; 三、漢諾塔問(wèn)題三、漢諾塔問(wèn)題BC一個(gè)古典的數(shù)學(xué)問(wèn)題：一個(gè)古典的數(shù)學(xué)問(wèn)題： 古代有一個(gè)梵塔，塔內(nèi)有古代有一個(gè)梵

8、塔，塔內(nèi)有3個(gè)座個(gè)座A、B、C，開始時(shí)，開始時(shí)A座上有座上有64個(gè)盤子，盤子大小不等，大的在下，小個(gè)盤子，盤子大小不等，大的在下，小的在上。的在上。 有一個(gè)老和尚想把這有一個(gè)老和尚想把這64個(gè)盤子從個(gè)盤子從A座移動(dòng)到座移動(dòng)到C座，每座，每次只允許移動(dòng)一個(gè)盤，且在移動(dòng)過(guò)程中，在每個(gè)次只允許移動(dòng)一個(gè)盤，且在移動(dòng)過(guò)程中，在每個(gè)座上都始終保持座上都始終保持大盤在下，小盤在上大盤在下，小盤在上。在移動(dòng)過(guò)。在移動(dòng)過(guò)程中可以利用程中可以利用B 座，寫出移動(dòng)步驟。座，寫出移動(dòng)步驟。An個(gè)盤子個(gè)盤子ABC動(dòng)畫演示：動(dòng)畫演示：分析分析3個(gè)盤子的情況：個(gè)盤子的情況：1. 將將A座上座上2個(gè)盤子移到個(gè)盤子移到B座座

9、（借助（借助C）；）；2. 將將A座上座上1個(gè)盤子移到個(gè)盤子移到C座；座；3. 將將B座上座上2個(gè)盤子移到個(gè)盤子移到C座座 （借助（借助A）。）。其中第其中第2 步可以直接實(shí)現(xiàn)。步可以直接實(shí)現(xiàn)。第第1、3步還需要遞歸分解。步還需要遞歸分解。A B CA BCA B C遞歸分解：遞歸分解：第第1 步步將將A座上座上2個(gè)盤子移到個(gè)盤子移到B座（借助座（借助C），），分解為：分解為：1.1 將將A上一個(gè)盤子從上一個(gè)盤子從A移到移到C；1.2 將將A上一個(gè)盤子從上一個(gè)盤子從A移到移到B；1.3 將將C上一個(gè)盤子從上一個(gè)盤子從C移到移到B。A BC1.1A BC1.2A BC1.3A B C3.第第3步

10、步將將B座上座上2個(gè)盤子移到個(gè)盤子移到C座座 （借助（借助A），），分解為：分解為：3.1 將將B上一個(gè)盤子從上一個(gè)盤子從B移到移到A；3.2 將將B上一個(gè)盤子從上一個(gè)盤子從B移到移到C；3.3 將將A上一個(gè)盤子從上一個(gè)盤子從A移到移到C。將以上綜合起來(lái)，可得到移動(dòng)將以上綜合起來(lái)，可得到移動(dòng)3個(gè)盤子的步驟為：個(gè)盤子的步驟為：AC，A B，C B，A C，B A，B C，A C。共經(jīng)歷共經(jīng)歷7（=231）步。）步?？梢酝浦?，可以推知，移動(dòng)移動(dòng) n 個(gè)盤子需要經(jīng)個(gè)盤子需要經(jīng)歷歷2 n 1。1. 將將A 座上座上n-1個(gè)盤子借助個(gè)盤子借助C 座移到座移到B 座上座上 ；2. 將將A 座上剩下的座上剩

11、下的1個(gè)盤子移到個(gè)盤子移到C 座上；座上；3. 將將B 座上座上n-1個(gè)盤子借助個(gè)盤子借助A 座移到座移到C 座上座上 。將第將第1步和第步和第3步表示為：步表示為： 將將“a” 座上座上n-1個(gè)盤子借助個(gè)盤子借助“b”座移到座移到“c”座。只是在第座。只是在第1 步和第步和第3 步中，步中，one、two、three和和A、B、C的對(duì)應(yīng)關(guān)的對(duì)應(yīng)關(guān)系不同。系不同。對(duì)第對(duì)第1步，對(duì)用關(guān)系是：步，對(duì)用關(guān)系是：aA，bC，cB。對(duì)第對(duì)第3步，對(duì)用關(guān)系是：步，對(duì)用關(guān)系是：aB，bA，cC。因此，可以將上面的因此，可以將上面的3個(gè)步驟分成個(gè)步驟分成兩類操作兩類操作： 將將n-1個(gè)盤子從一個(gè)座移到另一個(gè)個(gè)

12、盤子從一個(gè)座移到另一個(gè) 座上（座上（n1） ； 將將1個(gè)盤子從一個(gè)座移到另一個(gè)個(gè)盤子從一個(gè)座移到另一個(gè) 座上；座上；分別用兩個(gè)函數(shù)來(lái)實(shí)現(xiàn)這兩類操作。分別用兩個(gè)函數(shù)來(lái)實(shí)現(xiàn)這兩類操作。hanoi (n, a, b, c) 表示表示“ 將將n 個(gè)盤子從個(gè)盤子從a 座借助座借助b 座移到座移到c 座。座。a、b、c對(duì)應(yīng)不同情況的對(duì)應(yīng)不同情況的 A、B、C。將將n 個(gè)盤子從個(gè)盤子從A 座移到座移到C 座，可以分解為座，可以分解為3個(gè)步驟個(gè)步驟：第二步：第二步：將將A上剩下的一個(gè)上剩下的一個(gè) 移至移至C上上.第一步：先將第一步：先將A A塔塔n-1n-1個(gè)盤個(gè)盤 子借助于子借助于C C移至移至B B上上第

13、三步：第三步：將將B上上n-1個(gè)盤個(gè)盤 子借助于子借助于A移至移至C上上.第一步和第三部第一步和第三部為同一問(wèn)題為同一問(wèn)題,都為都為n-1個(gè)盤子借助于一個(gè)空塔移至另一塔上。個(gè)盤子借助于一個(gè)空塔移至另一塔上。算法分析：算法分析：/ 漢諾塔漢諾塔 # include void hanoi ( int n, char a, char b, char c ) if ( n = 1 ) hanoi ( n-1, a, c, b ) ; printf(“%c - %cn”, a , c) ; hanoi ( n-1, b, a, c ) ; void main () int n ; printf( Inp

14、ut the number of diskes:n “) ; scanf(“%d”,&n) ; hanoi ( n, A , B , C ) ; 源程序：源程序：hanoi(n, a, b, c)表示n個(gè)盤個(gè)盤子從從a塔借助于b塔(空)移至c塔。調(diào)調(diào)用時(shí)時(shí)塔用字符常量A，B ，C表示。四、課堂練習(xí)四、課堂練習(xí)#include long f(int n); /* 函數(shù)原型聲明函數(shù)原型聲明 */void main(void) long Value; int n; printf(Please input a number: ); do scanf(%d,&n); if(n 0) pr

15、intf(Data error! ); while(n 0); /* 如果輸入如果輸入n0,打印提示并重新輸入打印提示并重新輸入 */ Value = f(n); /* 調(diào)用函數(shù)調(diào)用函數(shù) */ printf(f(%d) = %ldn,n,Value);【練習(xí)題練習(xí)題】要求能夠輸出要求能夠輸出斐波那契數(shù)列斐波那契數(shù)列第第n個(gè)數(shù)是什么個(gè)數(shù)是什么，斐波那契數(shù)列定義為斐波那契數(shù)列定義為：00111)2()1()(nnnnfnfnf/* 函數(shù)名：函數(shù)名：f */* 功功 能：遞歸求斐波那契數(shù)列能：遞歸求斐波那契數(shù)列 */* 參參 數(shù)：數(shù)：n(整型整型) */* 返回值：項(xiàng)序?yàn)榉祷刂担喉?xiàng)序?yàn)閚的遞歸求斐波那契數(shù)列值的遞歸求斐波那契數(shù)列值(長(zhǎng)整型長(zhǎng)整型) */long f(int n) long y; if(n = 0) y = 0; else if(n = 1