【C語言】函數遞歸 - 詳解詳情 - 遞歸,迭代,斐波那契數,Html,CSS,前端開發 mb61c46a7ab1eee 博客

前言：

在 C 語言函數學習之旅中，遞歸是一個繞不開的重要話題。它不僅是一種編程技巧，更是一種解決問題的獨特思路。本文將從遞歸的基本概念出發，深入剖析其限制條件，通過實例演示遞歸的應用，並對比遞歸與迭代的優劣，幫助你徹底掌握 C 語言中的函數遞歸。

一、遞歸是什麼？

遞歸，從字面意義上看，包含 “遞” 和 “歸” 兩層含義。在 C 語言中，遞歸本質上是函數自己調用自己的一種行為，它將一個大型複雜的問題層層拆解為與原問題相似但規模更小的子問題，直到子問題無法再拆分，最終通過子問題的解逐步推導出原問題的解。

1.1遞歸的基本形式

#include <stdio.h>
  int main()
  {
  printf("hehe\n");
  main();// main函數中調用了main函數
  return 0;
  }

這段代碼中，main函數在自身內部調用了自己，符合於函數遞歸的定義。但需要注意的是，這段代碼由於缺乏終止條件，最終會陷入死遞歸，導致棧溢出（Stack overflow）的錯誤，出現類似於以下的提示：

“0x7BF20907 (ucrtbased.d11)(test.exe 中) 處有未經
處理的異常：0xC0000OP:Stack overflow (參數
：0x00000000, 0x00602000)”

1.2 遞歸的核心思想

遞歸的核心思想是 “大事化小”。比如要解決一個複雜問題A，我們可以將其拆解為問題 B，問題 B 的解決方法與問題 A`相似但規模更小；接着再將問題 B 拆解為問題 C，以此類推，直到拆解出的子問題可以直接解決（即遞歸的終止條件），然後再從子問題的解逐步迴歸，得到原問題的解。

二、遞歸的限制條件

並非任意函數自己調用自己都能構成有效的遞歸，有效的遞歸必須滿足兩個必要條件，這兩個條件缺一不可，否則就會出現死遞歸。

2.1 存在終止條件

遞歸必須存在一個明確的限制條件，當滿足這個條件時，遞歸將不再繼續。這個終止條件是遞歸能夠正常結束的關鍵，它就像遞歸的 “剎車”，防止遞歸無限進行下去。

2.2 逐步接近終止條件

在每次遞歸調用過程中，函數的參數或狀態必須逐漸接近遞歸的終止條件。也就是説，每一次遞歸調用都應該讓問題的規模更小，使得問題一步步向可直接解決的方向靠近。

三、遞歸實例解析

論結合實踐才能更好地理解遞歸，下面我們通過兩個經典實例，詳細的講解一下遞歸的應用過程。

3.1 實例 1：求 n 的階乘

一個正整數的階乘（factorial）是所有小於及等於該數的正整數的積，並且規定 0 的階乘為 1。自然數 n 的階乘記作 n!，其數學公式為：
當 n = 0 時，n! = 1；
當 n > 0 時，n! = n × (n - 1) ! 。

問題分析

從公式可以看出，求 n 的階乘可以拆解為求 n 乘以 (n - 1) 的階乘，而求 (n - 1) 的階乘又可以拆解為 (n - 1) 乘以 (n - 2) 的階乘，以此類推，直到拆解到求 0 的階乘（結果為 1），此時遞歸終止，再逐步迴歸計算出原問題的解。

舉例
5 ! = 5* 4* 3* 2 14 ! = 43* 2* 1 所以：5 ! = 4 !

代碼實現

#include <stdio.h>
  // 定義遞歸函數計算n的階乘
  int Fact(int n)
  {
  // 遞歸終止條件：n == 0時，返回1
  if (n == 0)
  return 1;
  // 遞歸調用：n > 0時，返回n乘以(n - 1)的階乘
  else
  return n * Fact(n - 1);
  }
  int main()
  {
  int n = 0;
  // 輸入要計算階乘的數字
  scanf("%d", &n);
  // 調用遞歸函數計算階乘
  int ret = Fact(n);
  // 輸出結果
  printf("%d\n", ret);
  return 0;
  }

運行結果與推演

當輸入 n = 5 時，程序運行結果為 120，符合 5! = 5×4×3×2×1 = 120 的預期。我們來推演一下遞歸過程：

Fact(5) = 5 × Fact(4)
Fact(4) = 4 × Fact(3)
Fact(3) = 3 × Fact(2)
Fact(2) = 2 × Fact(1)
Fact(1) = 1 × Fact(0)
Fact (0) = 1（遞歸終止）
然後開始迴歸計算：
Fact(1) = 1 × 1 = 1
Fact(2) = 2 × 1 = 2
Fact(3) = 3 × 2 = 6
Fact(4) = 4 × 6 = 24
Fact(5) = 5 × 24 = 120

3.2 實例 2：順序打印一個整數的每一位

問題分析

輸入一個整數 m，要求按照順序打印出該整數的每一位。例如，輸入 1234，輸出 1 2 3 4；輸入 520，輸出 5 2 0。

要解決這個問題，首先需要思考如何獲取整數的每一位。對於一個多位數，通過取餘運算（%10）可以得到其最低位，通過整除運算（/10）可以去掉最低位。但直接使用這種方法得到的數字順序是倒着的，比如 1234，先得到 4，再得到 3，接着得到 2，最後得到 1。

這時候就可以利用遞歸的思想：要打印 1234 的每一位，可以先打印 123 的每一位，再打印 1234 的最低位 4；要打印 123 的每一位，可以先打印 12 的每一位，再打印 123 的最低位 3；以此類推，直到要打印的數字是一位數時，直接打印該數字，遞歸終止。

代碼實現

#include <stdio.h>
  // 定義遞歸函數順序打印整數的每一位
  void Print(int n)
  {
  // 遞歸終止條件：當n是一位數時，直接打印
  if (n > 9)
  {
  // 遞歸調用：先打印n去掉最低位後的數字的每一位
  Print(n / 10);
  }
  // 打印n的最低位
  printf("%d ", n % 10);
  }
  int main()
  {
  int m = 0;
  // 輸入要打印每一位的整數
  scanf("%d", &m);
  // 調用遞歸函數打印每一位
  Print(m);
  return 0;
  }

運行結果與推演

當輸入 m = 1234 時，程序運行結果為 1 2 3 4，符合預期。
同樣我們可以來推演遞歸過程：

Print (1234)：1234 > 9，調用 Print (123)，之後打印 1234%10 = 4
Print (123)：123 > 9，調用 Print (12)，之後打印 123%10 = 3
Print (12)：12 > 9，調用 Print (1)，之後打印 12%10 = 2
Print (1)：1 <= 9，直接打印 1%10 = 1（遞歸終止）
最終打印順序為 1 2 3 4。

四、遞歸與迭代

遞歸雖然是一種簡潔的編程技巧，但並非在所有場景下都是最優選擇，很多時候迭代（通常指循環）是更好的替代方案。下面我們來對比遞歸與迭代的特點，並通過實例分析何時該使用遞歸，何時該使用迭代。

4.1 遞歸的優缺點

優點

代碼簡潔易懂：遞歸能夠直接反映問題的數學模型，使得代碼邏輯更加清晰，便於理解和編寫。比如求 n 的階乘，遞歸代碼直接對應階乘的數學公式，非常直觀。
解決複雜問題更有優勢：對於一些複雜問題，如漢諾塔問題、樹的遍歷等，使用遞歸可以將問題分解為更小的子問題，降低問題的複雜度，而使用迭代實現則可能非常繁瑣。

缺點

棧溢出風險：在 C 語言中，每一次函數調用都會在棧區申請一塊棧幀空間來保存局部變量等信息。如果遞歸層次過深，會佔用大量的棧空間，導致棧溢出錯誤。
效率較低：遞歸過程中存在函數調用的開銷，而且可能會出現大量重複計算的情況，導致程序運行效率降低。

4.2 迭代的優缺點

優點

效率高：迭代通過循環實現，避免了頻繁的函數調用開銷，也不會出現重複計算的問題（除非代碼邏輯設計不當），運行效率更高。
內存佔用少：迭代不需要額外的棧幀空間，內存佔用相對較少，不存在棧溢出的風險。

缺點

代碼邏輯可能複雜：對於一些複雜問題，使用迭代實現時，代碼邏輯可能會比較繁瑣，不易理解和維護。

4.3 實例對比：求第 n 個斐波那契數

斐波那契數的數學定義為：
當 n <= 2 時，Fib (n) = 1；
當 n > 2 時，Fib (n) = Fib (n - 1) + Fib (n - 2)。
根據這個定義，我們能很容易寫出遞歸代碼：

#include <stdio.h>
  int Fib(int n)
  {
  if (n <= 2)
  return 1;
  else
  return Fib(n - 1) + Fib(n - 2);
  }
  int main()
  {
  int n = 0;
  scanf("%d", &n);
  int ret = Fib(n);
  printf("%d\n", ret);
  return 0;
  }

但當 n = 50 時，程序需要很長時間才能算出結果，效率極低。這是因為遞歸過程中存在大量重複計算，我們通過一個計數器來統計第 3 個斐波那契數的計算次數：

#include <stdio.h>
  int count = 0;
  int Fib(int n)
  {
  if (n == 3)
  count++;// 統計第3個斐波那契數被計算的次數
  if (n <= 2)
  return 1;
  else
  return Fib(n - 1) + Fib(n - 2);
  }
  int main()
  {
  int n = 0;
  scanf("%d", &n);
  int ret = Fib(n);
  printf("%d\n", ret);
  printf("count = %d\n", count);
  return 0;
  }

運行結果

40
102334155

count = 39088169

當輸入 n = 40 時，輸出結果中 count = 39088169，這意味着第 3 個斐波那契數被重複計算了近 4000 萬次，大量的重複計算嚴重影響了程序效率。

4.4 迭代實現的優勢

針對斐波那契數的計算，我們可以使用迭代的方式來避免重複計算。由於斐波那契數的前兩個數都是 1，從第三個數開始，每個數都是前兩個數的和.
因此我們可以通過循環從前往後依次計算：

#include <stdio.h>
  int Fib(int n)
  {
  // 初始化前兩個斐波那契數
  int a = 1;
  int b = 1;
  // 存儲當前斐波那契數，初始值為1（當n <= 2時）
  int c = 1;
  // 循環計算從第3個到第n個斐波那契數
  while (n > 2)
  {
  c = a + b;
  a = b;
  b = c;
  n--;
  }
  return c;
  }
  int main()
  {
  int n = 0;
  scanf("%d", &n);
  int ret = Fib(n);
  printf("%d\n", ret);
  return 0;
  }

使用迭代實現後，即使 n = 100，程序也能快速計算出結果，效率遠高於遞歸實現。

4.5 遞歸與迭代的選擇建議

當問題的遞歸實現簡潔易懂，且遞歸層次不深，不存在大量重複計算時，可以選擇遞歸。例如求 n 的階乘、順序打印整數的每一位等。
當遞歸層次較深，或者存在大量重複計算時，應優先選擇迭代。例如求第 n 個斐波那契數。
對於一些複雜問題，如漢諾塔問題、樹的遍歷等，遞歸實現具有明顯優勢，此時可以選擇遞歸。

mb61c46a7ab1eee 博客

mb61c46a7ab1eee 博客

博客 / 詳情