萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

C 語言遞迴函數詳解:原理、條件與經典範例

什麼是遞迴?

在 C 語言中,函數可以直接或間接呼叫自己,這種機制稱為「遞迴」。直接遞迴指函數內部直接呼叫自身;間接遞迴則是函數 A 呼叫函數 B,B 再呼叫 A,形成呼叫鏈。本文重點探討直接遞迴。

遞迴必須滿足的三個條件

  1. 問題可分解為同類子問題: 原問題能轉化為規模較小、解法相同的子問題(參數有規律遞增/遞減)。
  2. 遞迴能實際解決問題: 相較於迭代,遞迴能更簡潔地表達邏輯(如樹遍歷、分治演算法)。
  3. 必須有明確的終止條件: 也就是「基準情況」,避免無限遞迴導致堆疊溢位。

經典範例:階乘計算

數學定義:n! = n × (n-1)!,且 0! = 1! = 1。遞迴關係明確,終止條件為 n <= 1。

程式碼實作

#include <stdio.h>

long long factorial(int n) {
    if (n == 0 || n == 1) return 1;      // 終止條件
    return n * factorial(n - 1);         // 遞迴呼叫
}

int main() {
    int m;
    printf("請輸入非負整數: ");
    scanf("%d", &m);
    if (m < 0) {
        printf("輸入錯誤!\n");
    } else {
        printf("%d! = %lld\n", m, factorial(m));
    }
    return 0;
}

遞迴執行流程分析(以 5! 為例)

每次呼叫都會在記憶體堆疊區建立新的活化記錄,包含參數、區域變數、返回位址:

  1. factorial(5) 呼叫 factorial(4) → 暫停等待
  2. factorial(4) 呼叫 factorial(3) → 暫停等待
  3. ... 直到 factorial(1) 返回 1
  4. 逐層回傳:2*1=2 → 3*2=6 → 4*6=24 → 5*24=120

此過程中,每一層的區域變數 n 獨立存在於不同的堆疊幀中,互不干擾。

遞迴的優缺點與記憶體模型

優點缺點
程式碼簡潔、邏輯清晰,適合樹、圖、分治等問題每層呼叫消耗堆疊空間,深度過大導致 Stack Overflow
天然符合數學歸納定義函數呼叫開銷大,執行效率通常低於迭代

記憶體釋放機制: 當函數執行完畢返回時,系統自動釋放該層堆疊幀,恢復上一層的變數與返回點。

所有遞迴皆可轉為迭代

理論上任何遞迴程式都能改寫為迴圈+堆疊的非遞迴形式,但程式碼會變複雜。選擇遞迴還是迭代,取決於可讀性與效能需求的權衡。

總結

遞迴是強大的程式設計工具,核心在於「找出子問題結構」與「設定正確終止條件」。初學者建議從階乘、費波納契、漢諾塔等經典題目入手,並在紙上畫出呼叫堆疊圖,深入理解記憶體與流程變化。

copyright © 萬盛學電腦網 all rights reserved