# 6.C語言函數的遞歸調用
一個函數在它的函數體內調用它自身稱為遞歸調用。這種函數稱為遞歸函數。C語言允許函數的遞歸調用。在遞歸調用中,主調函數又是被調函數。執行遞歸函數將反復調用其自身,每調用一次就進入新的一層。例如有函數f如下:
~~~
int f(int x){
int y;
z=f(y);
return z;
}
~~~
這個函數是一個遞歸函數。但是運行該函數將無休止地調用其自身,這當然是不正確的。為了防止遞歸調用無終止地進行,必須在函數內有終止遞歸調用的手段。常用的辦法是加條件判斷,滿足某種條件后就不再作遞歸調用,然后逐層返回。下面舉例說明遞歸調用的執行過程。
【例8-5】用遞歸法計算n!
用遞歸法計算n!可用下述公式表示:
? ? n!=1 ? ? ? ? ?(n=0,1)
? ? n×(n-1)!??? (n>1)
按公式可編程如下:
~~~
long ff(int n){
long f;
if(n<0) printf("n<0,input error");
else if(n==0||n==1) f=1;
else f=ff(n-1)*n;
return(f);
}
main(){
int n;
long y;
printf("\ninput a inteager number:\n");
scanf("%d",&n);
y=ff(n);
printf("%d!=%ld",n,y);
}
~~~
程序中給出的函數ff是一個遞歸函數。主函數調用ff 后即進入函數ff執行,如果n<0,n==0或n=1時都將結束函數的執行,否則就遞歸調用ff函數自身。由于每次遞歸調用的實參為n-1,即把n-1的值賦予形參n,最后當n-1的值為1時再作遞歸調用,形參n的值也為1,將使遞歸終止。然后可逐層退回。
下面我們再舉例說明該過程。設執行本程序時輸入為5,即求5!。在主函數中的調用語句即為y=ff(5),進入ff函數后,由于n=5,不等于0或1,故應執行f=ff(n-1)*n,即f=ff(5-1)*5。該語句對ff作遞歸調用即ff(4)。
進行四次遞歸調用后,ff函數形參取得的值變為1,故不再繼續遞歸調用而開始逐層返回主調函數。ff(1)的函數返回值為1,ff(2)的返回值為1*2=2,ff(3)的返回值為2*3=6,ff(4)的返回值為6*4=24,最后返回值ff(5)為24*5=120。
【例8-5】也可以不用遞歸的方法來完成。如可以用遞推法,即從1開始乘以2,再乘以3…直到n。遞推法比遞歸法更容易理解和實現。但是有些問題則只能用遞歸算法才能實現
- 前言
- 一. C語言概述
- 1.C語言的發展及其版本
- 2.C語言工作原理和運行機制
- 3.C語言編譯器(開發工具|IDE)推薦
- 4.C語言的特點
- 5.第一個C語言程序
- 6.C語言輸出函數(printf)和輸入函數(scanf)
- 7.C語言程序的結構特點
- 8.C語言字符集
- 9.C語言詞匯
- 二. C語言算法
- 1.什么是算法|算法的概念
- 2.簡單的C語言算法舉例
- 3.C語言算法的特性
- 4.用流程圖表示算法
- 5.三種基本結構的流程圖
- 6.用N-S流程圖表示算法
- 7.用計算機語言表示算法
- 三. 數據類型和運算符
- 1.C語言的數據類型
- 2.C語言常量與變量
- 3.C語言整型數據
- 4.C語言實型數據
- 5.C語言字符型數據
- 6.C語言變量賦初值
- 7.C語言數據類型轉換
- 8.C語言算術運算符和算術表達式
- 9.C語言賦值運算符和賦值表達式
- 10.C語言逗號運算符和逗號表達式
- 四. 順序程序設計
- 1.C語言語句概述
- 2.C語言賦值語句詳解
- 3.C語言數據的輸入輸出
- 4.C語言字符的輸入輸出
- 7.C語言順序結構程序設計舉例
- 五. 分支結構
- 1.C語言關系運算符和表達式
- 2.C語言邏輯運算符和表達式
- 3.C語言if語句詳解
- 4.C語言switch語句的用法詳解
- 5.C語言條件運算符和條件表達式
- 6.C語言分支結構程序舉例
- 六. 循環控制
- 1.C語言循環控制概述
- 2.C語言goto語句以及用goto語句構成循環
- 3.C語言while語句的用法
- 4.C語言do-while語句的用法
- 5.C語言for語句用法詳解
- 6.C語言幾種循環的比較
- 7.C語言break和continue語句的用法
- 8.C語言循環控制程序舉例
- 七. C語言數組
- 1.C語言一維數組的定義和引用
- 2.C語言二維數組的定義和引用
- 3.C語言字符數組及其應用
- 4.C語言常用字符串處理函數
- 5.C語言數組應用舉例
- 6.C語言數組小結
- 八. C語言函數
- 1.C語言函數概述
- 2.C語言函數的定義
- 3.C語言函數的參數和返回值
- 4.C語言函數的調用
- 5.C語言函數的嵌套調用
- 6.C語言函數的遞歸調用
- 7.C語言數組作為函數參數
- 8.C語言局部變量和全局變量
- 9.C語言變量的存儲類別
- 九. 預處理命令
- 1.C語言預處理概述
- 2.C語言無參數宏定義
- 3.C語言帶參數宏定義
- 4.C語言文件包含命令
- 5.C語言條件編譯詳解
- 6.C語言預處理指令總結
- 十. C語言指針
- 1.C語言指針的概念
- 2.C語言指針變量
- 3.C語言指針變量作為函數參數
- 4.C語言指針變量的運算
- 5.C語言數組指針
- 6.C語言通過指針引用數組
- 7.C語言數組名作函數參數
- 8.C語言指向多維數組的指針
- 9.C語言字符串指針
- 10.C語言字符串指針變量與字符數組的區別
- 11.C語言函數指針變量
- 12.C語言指針型函數
- 13.C語言指針數組的概念
- 14.C語言指向指針的指針
- 15.C語言main函數參數
- 16.關于指針的總結
- 十一. 結構體和共用體
- 1.C語言結構體的定義
- 2.C語言結構類型變量的說明
- 3.C語言結構變量成員的表示方法
- 4.C語言結構變量的賦值
- 5.C語言結構變量的初始化
- 6.C語言結構體數組的定義
- 7.C語言指向結構體變量的指針
- 8.C語言指向結構體數組的指針
- 9.C語言結構體指針變量作函數參數
- 10.C語言動態存儲分配
- 11.C語言鏈表的概念
- 12.C語言枚舉類型
- 13.C語言類型定義符typedef
- 十二. 位運算
- 1.C語言位運算符詳解
- 2.C語言位域(位段)
- 3.關于位運算的總結
- 十三. 文件操作
- 1.C語言文件概述
- 2.C語言文件指針
- 3.C語言文件的打開與關閉
- 4.C語言文件的讀寫
- 5.C語言文件的隨機讀寫
- 6.C語言文件檢測函數
- 7.C語言庫文件(頭文件)有哪些
- 8.文件操作小結