C語言中的遞迴

上一頁
下一頁

遞迴是指一個函式呼叫自身的過程。C語言允許編寫這樣的函式，這些函式透過將複雜問題分解成簡單易處理的問題來呼叫自身以解決複雜問題。這些函式被稱為遞迴函式。

什麼是C語言中的遞迴函式？

C語言中的遞迴函式是一個函式，它呼叫自身。當某個問題以自身來定義時，就會使用遞迴函式。雖然它涉及迭代，但使用迭代方法來解決此類問題可能會很繁瑣。遞迴方法為看似複雜的問題提供了一種非常簡潔的解決方案。

語法

一個通用的遞迴函式看起來像這樣：

void recursive_function(){
   recursion();   // function calls itself
}

int main(){
   recursive_function();
}

在使用遞迴時，程式設計師需要注意定義函式的退出條件，否則它將進入無限迴圈。

為什麼在C語言中使用遞迴？

遞迴用於執行復雜的任務，例如樹和圖結構遍歷。流行的遞迴程式設計解決方案包括階乘、二分查詢、樹遍歷、漢諾塔、國際象棋中的八皇后問題等。

遞迴程式變得簡潔，但不容易理解。即使程式碼的大小可能減少，它也需要更多處理器資源，因為它涉及對函式的多次IO呼叫。

使用遞迴計算階乘

遞迴函式對於解決許多數學問題非常有用，例如計算數字的階乘、生成斐波那契數列等。

遞迴最流行的例子是階乘的計算。在數學上，階乘定義為：

 
n! = n X (n-1)!

可以看出，我們使用階乘本身來定義階乘。因此，這是一個適合編寫遞迴函式的案例。讓我們擴充套件上述定義來計算5的階乘值。

5! = 5 X 4!
   5 X 4 X 3!
   5 X 4 X 3 X 2!
   5 X 4 X 3 X  2 X 1!
   5 X 4 X 3 X  2 X 1
   = 120

雖然我們可以使用迴圈執行此計算，但它的遞迴函式涉及透過遞減數字來連續呼叫自身，直到它達到1。

示例：非遞迴階乘函式

以下程式演示瞭如何使用非遞迴函式來計算數字的階乘：

#include <stdio.h>
#include <math.h>

// function declaration
int factorial(int);

int main(){
   int a = 5;
   int f = factorial(a);
   
   printf("a: %d \n", a);
   printf("Factorial of a: %d", f);
}
int factorial(int x){
   int i;
   int f = 1;
   
   for (i = 5; i >= 1; i--){
      f *= i;
   }
   return f;
}

輸出

執行此程式碼時，它將產生以下輸出：

a: 5 
Factorial of a: 120

示例：遞迴階乘函式

現在讓我們為計算給定數字的階乘編寫一個遞迴函式。

以下示例使用遞迴函式計算給定數字的階乘：

#include <stdio.h>
#include <math.h>

/* function declaration */
int factorial(int i){

   if(i <= 1){
      return 1;
   }
   return i * factorial(i - 1);
}
int main(){
   int a = 5;
   int f = factorial(a);
   
   printf("a: %d \n", a);
   printf("Factorial of a: %d", f);
   return 0;
}

輸出

執行程式碼並檢查其輸出：

a: 5 
Factorial of a: 120

當main()函式透過傳遞變數“a”來呼叫factorial()函式時，它的值將儲存在“i”中。factorial()函式連續呼叫自身。

在每次呼叫中，"i"的值在減少1後乘以其先前值，直到它達到1。當它達到1時，從引數的初始值到1之間所有值的乘積將返回到main()函式。

使用遞迴進行二分查詢

讓我們再看一個例子來了解遞迴是如何工作的。手頭的問題是在陣列中檢查給定數字是否存在。

雖然我們可以使用for迴圈並比較每個數字來對列表中的某個數字進行順序查詢，但順序查詢效率不高，尤其是在列表過長的情況下。

二分查詢演算法檢查索引“start”是否大於索引“end”。根據變數“mid”處的值，再次呼叫該函式以搜尋元素。

我們有一個按升序排列的數字列表。然後我們找到列表的中點，並將檢查限制在中點的左側或右側，具體取決於所需數字是否小於或大於中點處的數字。

示例：遞迴二分查詢

以下程式碼實現了遞迴二分查詢技術：

#include <stdio.h>

int bSearch(int array[], int start, int end, int element){
   
   if (end >= start){
      
      int mid = start + (end - start ) / 2;
      
      if (array[mid] == element)
         return mid;
      
      if (array[mid] > element)
         return bSearch(array, start, mid-1, element);
         return bSearch(array, mid+1, end, element);
   }
   return -1;
}

int main(void){
   int array[] = {5, 12, 23, 45, 	49, 67, 71, 77, 82};
   int n = 9;
   int element = 67;
   int index = bSearch(array, 0, n-1, element);
   
   if(index == -1 ){
      printf("Element not found in the array ");
   }
   else{
      printf("Element found at index: %d", index);
   }
   return 0;
}

輸出

執行程式碼並檢查其輸出：

Element found at index: 5

使用遞迴生成斐波那契數列

在斐波那契數列中，一個數字是其前兩個數字的和。要生成斐波那契數列，第i個數字是i-1和i-2的加和。

示例

以下示例使用遞迴函式為給定數字生成斐波那契數列的前10個數字：

#include <stdio.h>

int fibonacci(int i){

   if(i == 0){
      return 0;
   }
   
   if(i == 1){
      return 1;
   }
   return fibonacci(i-1) + fibonacci(i-2);
}

int main(){
   
   int i;
   
   for (i = 0; i < 10; i++){
      
      printf("%d\t\n", fibonacci(i));
   
   } 
   return 0;
}

輸出

編譯並執行上述程式碼時，將產生以下結果：

0	
1	
1	
2	
3	
5	
8	
13	
21	
34

在程式中實現遞迴對於初學者來說比較困難。雖然任何迭代過程都可以轉換為遞迴過程，但並非所有遞迴案例都可以輕鬆地迭代表示。

列印頁面

上一頁
下一頁
廣告