1. 分割問題/各個擊破

2. 將問題縮小以逐步降低問題的困難度

概念性的遞迴乘法

m * n 可以寫成 m + m * (n-1)

在運用遞迴的概念時, 我們希望逐步縮小問題, 因為數值變小了一點, m * (n-1) 的確比 m * n 要容易一點點, 所以我們可以撰寫遞迴函數, 透過加法計算乘法,

設計的時候主要的核心在於如下的想法: "如果能夠計算出 x = m * (n-1), 則 m + x 就是程式要計算出來的結果了"

請注意函數中包含 1. m + xxx, 2. 呼叫遞迴函數計算 m * (n-1), 3. 遞迴的結束條件

int multiply(int m, int n)
{
    int ans;
    
    if (n == 1)
        ans = m;     /* simple case 結束 */
    else
        ans = m + multiply(m, n  - 1);  /* recursive step 遞迴 */
    
    return (ans);
}

簡易測試程式:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int x, y, z;
    printf("Please input two integers: ");
    scanf("%d%d", &x, &y);
    if (y > 0)
    {
        z = multiply(x, y);
        printf("%d * %d = %d\n", x, y, z);
    }
    else
        printf("y has to be positive!\n");
    system("pause");
    return 0;
}

測試結果:

1. 14 * 7 = 98
2. 19 * 123 = 2337
3. 123456 * 98765432 = 12193185172992
4. ...

稍後我們會嘗試練習使用遞迴函數來實作一個整數乘法群中的指數運算: a^b (mod p), 就會比這個範例要有意義得多

反序列印輸入的英文字:

下面這個遞迴的函數由鍵盤讀取指定個數的英文字, 然後以顛倒過來的順序列印它們, 例如以參數 5 呼叫時 reverse_input_words(5), 函數讀入下列五個字串:
the
course
of
human
events
並且反序列印出來如下:
events
human
of
course
the

程式設計的時候最主要的想法是 1. 先讀入第一個字串 "the", 2. 如果能夠執行一個工具, 讀入接下來的四個英文字串 "course", "of", "human", "events", 並且完成反序列印 "events", "human", "of", "course", 3. 我們只要執行這個工具, 最後再列印出 "the" 就大功告成了

程式碼: 注意包括下列部份 1. 讀取輸入字串, 2. 列印字串, 3. 遞迴呼叫, 4. 遞迴結束條件

void reverse_input_words(int n)
{
    char word[WORDSIZE];  /*  local variable for storing one word	*/
    
    if (n <= 1)    /* simple case: just one word to get and print	*/
    {
        scanf("%s", word);
        printf("%s\n", word);
    
    }      /* get this word; get and print the rest of the words in */
    else   /*       reverse order; then print this word             */
    {
        scanf("%s", word);
        reverse_input_words(n - 1);
        printf("%s\n", word);
    }
}

如果使用原始碼偵錯器追蹤程式執行的話,可以看到下列的函數呼叫以及程式動作順序:

呼叫 reverse_input_words, 參數為 3
       讀取第一個字串 "bits" 到字元陣列變數 word 中
       呼叫 reverse_input_words, 參數為 2
              讀取第二個字串 "and" 到字元陣列變數 word 中
              呼叫 reverse_input_words, 參數為 1
                     讀取第三個字串 "bytes" 到字元陣列變數 word 中
                     由字元陣列變數 word 中列印第三個字串 "bytes"
                     執行 return 敘述回到第二層的函數中
              由字元陣列變數 word 中列印第二個字串 "and"
              執行 return 敘述回到第一層的函數中
       由字元陣列變數 word 中列印第一個字串 "bits"
       執行 return 敘述回到呼叫 reverse_input_words(3) 的下一列

遞迴式 (recursive) vs. 疊代式 (iterative) 演算法設計:

所有運用遞迴方式設計的程式一定都可以換成疊代式的程式, 常常疊代式的程式裡需要設計些輔助的資料結構 (data structures), 尤其是堆疊 (stack)。疊代式的程式通常擁有比較好的執行效率, 而遞迴式的程式常常比較容易撰寫, 比較容易瞭解, 以計算階乘的程式為例:

遞迴式:

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

疊代式:

int factorial(int n)
{
    int i,product = 1;


    for  (i = n;  i > 1;  --i) 
        product = product * i;

    return (product);
}

接下來我們練習寫遞迴式的最大公因數程式:

如果我們要計算 gcd(273, 26) 的最大公因數, 計算 273 = 10 * 26 + 13, 然後計算 gcd(26, 13) 就是我們要的結果, 以遞迴函數撰寫如下:

int gcd(int m, int n)
{
    int ans;
    
    if (m % n == 0)
        ans = n;
    else
        ans = gcd(n, m % n);
    
    return ans;
}

請把這個程式和先前 疊代式 的程式比較一下

5

請撰寫一個遞迴函數計算 a^b (mod p), 其中 a,b,p 為非負整數

範例輸入及輸出

a=? > 3
b=? > 18132
p=? > 17

3^18132 = 13 (mod 17)

a=? > 17
b=? > 1765
p=? > 3

17^1765 = 2 (mod 3)

a=? > 2374859
b=? > 3029382
p=? > 36123

2374859^3029382 = 13195 (mod 36123)

(先不去用費馬小定理或是 Euler 定理: 指數先 mod \phi(p), 這裡 \phi(p) 是 Euler 的 Totient function。 這個實習最主要希望大家練習遞迴的寫法)

簡單想法:

1. 如果 b 是偶數, 可以先作出 a^b/2 (mod p) 再平方
   
2. 如果 b 是奇數, 可以先作出 a^(b-1)/2 (mod p), 平方, 再乘 a

記得每一次乘法都要 mod p, 才能夠控制數字的範圍不會太大而無法存放在整數變數裡

(以最後一個例子來說, 2374859*2374859=5639955269881 已經超過 32 位元的 int 了, 請用 64 位元的 long long int 來實作, 請注意 devcpp4.9.9.2, devcpp5.8.1以 printf 列印或是 scanf 讀取需要用 %I64d, 64 位元的常數請寫成 12345678901234LL)