遞歸調用函數專題-C語言

0| 前言

本小節主要學習一種自己嵌套自己的函數調用方法——遞歸調用

1| 示例

例如，在給定整數n的情況下，計算并輸入階乘n!的程序。

階乘函數的定義：

 int factorial(int n){
     int product;
     for (int i = 1; i <= n; i++){
         product = product * i;
     }
     return product;
 }

這個函數思想：使用了一個循環將1到n的數值依次相乘進行計算，并將得到的乘積作為結果返回。

用for循環解決問題

• 一個循環從1開始
• 一直不斷相乘，直到乘以n為止

2| 遞歸思想求解階乘

遞歸思想求解函數階乘

 int factorial(int n) {
     if (n==1){
         return 1;
     }
     return factorial(n - 1) * n;
 }

其實換一個角度在思考這個問題，n!可以看成 n*(n-1)!的乘積， 而(n-1)!又可以看作是(n-1)*(n-2)!的乘積….. 以此類推到 2 * 1 ， 代碼是不是更簡潔一點呢？

其實，像這種在一個函數的定義中調用自身的情況被稱為–遞歸調用

（1）頭遞歸

例如定義的函數：

 int factorial(int n){
     if (n == 1){
         return 1;
     }
     return factorial(n-1) * n; 
 }

如果傳入給函數factorial() 的n是5：

factorial(5) = 5 * factorial (4)

= 5 * 4 * factorial (3)

= 5 * 4 * 3 * factorial(2)

= 5 * 4 * 3 * 2 * factorial(1)

= 5 * 4 * 3 * 2 * 1

像這種返回一個包含本身函數的遞歸調用的這種遞歸設計，被稱為投遞歸。

（2）尾遞歸

與頭遞歸相對應的就是尾遞歸，尾遞歸的思想實現如下：

 int factorial(int n, int product){
     if (n == 0){
         return product;
     }
     product = product * n;
     return factorial(n-1, product);
 }

同樣也拿 n=5, 來了解一下程序的實現細節：

 factorial (5,1)  ~ factorial(n, product * n)
 = factorial(4,1*5) = factorial(4, 5)
 = factorial(3, 5*4) = factorial(3, 20)
 = factorial(2, 20*3) = factorial(2, 60)
 = factorial(1, 60*2) = factorial(1, 120)]
 = factorial(0, 120*1) = factorial(0, 120)
 = 120  ~ product

小伙伴沒有發現，尾遞歸的實現中，每一次函數遞歸調用都會將一個階段性的結果傳遞到下一次被調用的函數中，當最終的一般終止條件滿足時，把最終結果直接返回。