案例解說C語言遞歸函數

C語言遞歸函數是指在函數的定義中使用函數自身的方法，也就是一個函數在它的函數體内調用它自身。這種函數稱為遞歸函數。

遞歸函數的特點是：

- 存在限制條件，當符合這個條件時遞歸便不再繼續。

- 每次遞歸調用之後越來越接近這個限制條件。

- 執行遞歸函數将反複調用其自身，每調用一次就進入新的一層，當最内層的函數執行完畢後，再一層一層地由裡到外退出。

遞歸函數不是C語言的專利，Java、C#、JavaScript、PHP等其他程式設計語言也都支援遞歸函數。

遞歸函數在解決許多數學問題上起了至關重要的作用，比如計算一個數的階乘、生成斐波那契數列、漢諾塔問題等等。

下面我們通過一個求階乘的例子，看看遞歸函數到底是如何運作的。

#include <stdio.h>
//求n的階乘
long factorial(int n) {
  if (n == 0 || n == 1) {
	  return 1;
  } else {
 	 return factorial(n - 1) * n; // 遞歸調用
  }
}
int main() {
  int a;
  printf("Input a number: ");
  scanf("%d", &a);
  printf("Factorial (%d) = %ld\n", a, factorial(a));
  return 0;
}           

運作結果：

Input a number: 5↙
Factorial (5) = 120           

factorial()就是一個典型的遞歸函數。調用factorial()後即進入函數體，隻有當n==0或n==1時函數才會執行結束，否則就一直調用它自身。由于每次調用的實參為n-1，即把n-1的值賦給形參n，是以每次遞歸實參的值都減1，直到最後n-1的值為1時再作遞歸調用，形參n的值也為1，遞歸就終止了，會逐層退出。

要想了解遞歸函數，重點是了解它是如何逐層進入，又是如何逐層退出的。下面我們以5!為例進行講解。

**遞歸的進入**

1. 求5!，即調用factorial(5)。當進入factorial()函數體後，由于形參n的值為5，不等于0或1，是以執行factorial(n-1) * n ，也即執行factorial(4) * 5 。為了求得這個表達式的結果，必須先調用factorial(4)，并暫停其他操作。換句話說，在得到factorial(4)的結果之前，不能進行其他操作。這就是第一次遞歸。

2. 調用factorial(4)時，實參為4，形參n也為4，不等于0或1，會繼續執行factorial(n-1) * n ，也即執行factorial(3) * 4 。為了求得這個表達式的結果，又必須先調用factorial(3)。這就是第二次遞歸。

3. 以此類推，進行四次遞歸調用後，實參的值分别為3、2、1、0，形參n的值也相同。當實參為0時，形參n也為0，等于0或1，會執行return 1;語句，傳回1。這就是第五次遞歸，也是最後一次遞歸。

**遞歸的退出**

4. 當第五次遞歸傳回1後，第四次遞歸就可以繼續執行了。第四次遞歸的表達式是factorial(1) * 2 ，由于factorial(1)已經傳回了1，是以這個表達式的結果就是1 * 2 = 2 ，并傳回給第三次遞歸。

5. 當第四次遞歸傳回2後，第三次遞歸就可以繼續執行了。第三次遞歸的表達式是factorial(2) * 3 ，由于factorial(2)已經傳回了2，是以這個表達式的結果就是2 * 3 = 6 ，并傳回給第二次遞歸。

6. 當第三次遞歸傳回6後，第二次遞歸就可以繼續執行了。第二次遞歸的表達式是factorial(3) * 4 ，由于factorial(3)已經傳回了6，是以這個表達式的結果就是6 * 4 = 24 ，并傳回給第一次遞歸。

7. 當第二次遞歸傳回24後，第一次遞歸就可以繼續執行了。第一次遞歸的表達式是factorial(4) * 5 ，由于factorial(4)已經傳回了24，是以這個表達式的結果就是24 * 5 = 120 ，并傳回給主函數。

8. 當第一次遞歸傳回120後，主函數就可以繼續執行了。主函數會把120指派給factorial(a)，并輸出結果。

以上就是求階乘的例子中，遞歸函數的進入和退出過程。通過這個例子，我們可以看到：

- 每一層都有自己獨立的變量n和表達式factorial(n-1) * n ，它們不會互相幹擾。

- 每一層都要等待下一層傳回結果後才能繼續執行。

- 最内層的函數最先結束，最外層的函數最後結束。

使用遞歸函數的注意事項：

- 遞歸函數必須有一個明确的終止條件，也就是遞歸的出口，否則會導緻無限遞歸，造成棧溢出或者系統崩潰。

- 遞歸函數的效率通常比較低，因為它需要反複地調用自身，占用大量的棧空間和時間。是以，在能夠用循環解決的問題上，盡量避免使用遞歸函數。

- 遞歸函數的參數應該有規律地變化，使得每次遞歸調用都能夠向終止條件靠近。否則，遞歸函數可能陷入死循環，無法傳回結果。

- 遞歸函數中如果使用了靜态變量，那麼在整個遞歸過程中，這個靜态變量隻會被配置設定一次記憶體空間，并且在每次遞歸調用中都會被修改。是以，在使用靜态變量時要注意它的作用域和生命周期。

系列文章持續更新，如果覺得有幫助請點贊+關注！