c語言課件函數(shù)的遞歸調(diào)用

1、函數(shù)的遞歸調(diào)用在調(diào)用一個函數(shù)的過程中又出現(xiàn)直接或間接地調(diào)用函數(shù)本身的情況，稱為函數(shù)的遞歸調(diào)用。兩種形式的遞歸直接遞歸：f1中調(diào)用f1間接遞歸：f1中調(diào)用f2、f2再調(diào)用f1遞歸函數(shù)的編寫與使用應注意：遞歸函數(shù)一定要有出口示例遞歸函數(shù)執(zhí)行情況分析Fibonacci數(shù)列返回遞歸與數(shù)學歸納法的類比遞歸與數(shù)學歸納法的類比用數(shù)學歸納法證明:135(2n1)n2先設(shè)定 一個初始值當n=1時，證明成立 假設(shè)n=k時等式成立，推出n=k+1成立返回遞歸的解題思路先設(shè)定一個遞歸出口，一般是邊界情況將問題化為與原問題類似的子問題，子問題的參數(shù)類型、個數(shù)以及函數(shù)的返回值與原問題一致，只是在問題的規(guī)模上比原問題小.假

2、設(shè)子問題可以解決，利用子問題去解決原問題.返回遞歸例題P174 例題8.8 求階乘 n!1、遞歸出口，邊界情況 n=0或1時 n!=12、轉(zhuǎn)化為與原問題類似的子問題 n!= n(n-1)! 其中的子問題是 (n-1)!3、利用子問題去解決原問題： n!= n(n-1)!返回遞歸例題float fac(int n) float f; if(n0) printf(n0,dataerror!); else if(n=0,n=1) f=1; else f=fac(n-1)*n; return(f); 返回與原問題相類似，參數(shù)個數(shù)以及參數(shù)類型都一致遞歸框架float fac(int n) float f

3、; if(n=1) f=1； else f = fac(n-1). return(f); 返回根據(jù)實際需要確定函數(shù)名稱、參數(shù)個數(shù)，參數(shù)類型及函數(shù)返回值根據(jù)實際需要確定是否需要變量用條件判斷語句表示遞歸出口遞歸出口，一般是邊界情況遞歸調(diào)用，子問題的參數(shù)個數(shù)以及參數(shù)類型與原問題一致遞歸例題Fibonacci數(shù)列 P125 F(1)=1 (n=1) F(2)=1 (n=2) F(n)=F(n-1)+F(n-2) (n3)思考：1、遞歸的出口條件是什么？2、如何轉(zhuǎn)化為類似的子問題？3、函數(shù)的參數(shù)個數(shù)要幾個？類型是什么？函數(shù)返回值是什么？遞歸例題Hanoi問題Hanoi問題由分析可知：將個盤子從座移到座

4、可以分為以下3個步驟：(1) 將上個盤借助座先移到座上。(2) 把座上剩下的一個盤移到座上。(3) 將個盤從座借助于座移到座上。思考：1、函數(shù)要幾個參數(shù)？參數(shù)的類型是什么？2、函數(shù)的返回值是什么？3、遞歸調(diào)用的出口是什么？4、如何將原問題轉(zhuǎn)化為子問題？遞歸例題(1) 將上個盤借助座先移到座上。(2) 把座上剩下的一個盤移到座上。(3) 將個盤從座借助于座移到座上。 void hanoi(int n,char one,char two,char three) if(n=1) move(one,three); else hanoi(n-1,one,three,two); move(one,thre

5、e); hanoi(n-1,two,one,three); 編程求解：若一頭小母牛，從出生起第四個年頭開始每年生一頭母牛，按次規(guī)律，第n年時有多少頭母牛？年頭1 2 3 4 5 6 7 8 牛數(shù)1 1 1 2 3 4 6 9int cattle(int n) if(n=0) return 0; if(n=3) return 1; return cattle(n-1)+ cattle(n-3); 遞歸的實際過程 遞歸屬于函數(shù)的嵌套調(diào)用。調(diào)用函數(shù)時需要保存調(diào)用的一些現(xiàn)場參數(shù)等等，因此函數(shù)的調(diào)用需要占用內(nèi)存空間。當遞歸的次數(shù)很多時，消耗的內(nèi)存空間是相當可觀的。遞歸實際是以犧牲大量的存儲空間為代價的。

6、遞歸的實際過程 基本上所有遞歸都可以由循環(huán)來代替，但是，有些時候用遞歸較好，有些時候用循環(huán)較好。由于遞歸涉及函數(shù)的調(diào)用，要消耗棧的空間，同時還得花時間建立函數(shù)調(diào)用過程記錄，因此，通常優(yōu)先使用循環(huán)的方法。 注意：對于遞歸程序，在遞歸語句之前的語句，在遞歸之前執(zhí)行；在遞歸語句之后的語句，在遞歸返回之后執(zhí)行。內(nèi)部變量只在所在塊中有效，故稱局部變量。函數(shù)體是典型的塊，所以在函數(shù)聲明語句部分定義的變量也是局部變量。形式參數(shù)只在函數(shù)中有效，也是局部變量。遞歸的實際過程int age(int n) int c; if(n=1) c=10; else c=age(n-1)+2; return(c); 遞歸的實際過程int age(int n) int c; printf(“ n=%3d,n); if(n=1) c=10; else c=age(n-1)+2; printf(“ c=%3d”,c); return(c); n=5 n=4 n=3 n=2 n=1c=10 c=12 c=14 c=16 c=18遞歸的實際過程int age(int n) int c; if(n=1) c=10; else c=