程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> C語言基礎知識 >> C語言函數的遞歸調用

C語言函數的遞歸調用

編輯:C語言基礎知識
一個函數在它的函數體內調用它自身稱為遞歸調用,這種函數稱為遞歸函數。執行遞歸函數將反復調用其自身,每調用一次就進入新的一層。

【示例】用遞歸計算 n!。階乘 n! 的計算公式如下:

根據公式編程:
long factorial(int n){
    long result;

    if(n==0 || n==1){
        result = 1;
    }else{
        result = factorial(n-1) * n;  // 遞歸調用
    }

    return result;
}
這是一個典型的遞歸函數。調用factorial後即進入函數體,只有當 n==0 或 n==1 時函數才會執行結束,否則就一直調用它自身。

由於每次調用的實參為 n-1,即把 n-1 的值賦給形參 n,所以每次遞歸實參的值都減 1,直到最後 n-1 的值為 1 時再作遞歸調用,形參 n 的值也為1,遞歸就終止了,會逐層退出。

例如求 5!,即調用factorial(5)。當進入factorial函數體後,由於 n=5,不等於0或1,所以執行result = factorial(n-1) * n;,即result = factorial(5-1) * 5;,接下來也就是調用factorial(4)。這是第一次遞歸。

進行四次遞歸調用後,實參的值為 1,也就是調用factorial(1)。這時遞歸就結束了,開始逐層返回。factorial(1) 的值為 1,factorial(2) 的值為 1*2=2,factorial(3) 的值為 2*3=6,factorial(4) 的值為 6*4=24,最後返回值 factorial(5) 為 24*5=120。
注意:為了防止遞歸調用無終止地進行,必須在函數內有終止遞歸調用的手段。常用的辦法是加條件判斷,滿足某種條件後就不再作遞歸調用,然後逐層返回。
遞歸調用不但難於理解,而且開銷很大,如非必要,不推薦使用遞歸。很多遞歸調用可以用迭代(循環)來代替。

【示例】用迭代法求 n!。
long factorial(int n){
    int i;
    long result=1;

    if(n==0 || n==1){
        return 1;
    }

    for(i=1; i<=n; i++){
        result *= i;
    }
    return result;
}
關於函數調用的原理,請大家閱讀《C語言和內存》中的《棧的概念以及棧溢出》《一個函數在棧上到底是怎樣的》《詳細分析一個函數進棧出棧的例子》幾節,屆時你將會明白遞歸調用的開銷為什麼很大。
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved