C語言深入分析遞迴函數的實現

2022-04-15 19:00:07

一、遞迴的數學思想

遞迴是一種數學上分而自治的思想

遞迴需要有邊界條件

當邊界條件不滿足時，遞迴繼續進行
當邊界條件滿足時，遞迴停止

遞迴將大型複雜問題轉化為與原問題相同但規模較小的問題進行處理。

二、遞迴函數

函數體內部可以呼叫自己

遞迴函數

函數體中存在自我呼叫的函數

遞迴函數是遞迴的數學思想在程式設計中的應用

遞迴函數必須有遞迴出口
函數的無限遞迴將導致程式棧溢位而崩潰

三、遞迴函數設計技巧

遞迴模型的一般表示法

四、遞迴函數設計範例一

用遞迴的方法編寫函數求字串長度

程式碼如下：

#include <stdio.h>
 
int strlen_r(const char* s)
{
    if( *s )
    {
        return 1 + strlen_r(s+1);
    }
    else
    {
        return 0;
    }
}
 
int main()
{
    printf("%dn", strlen_r("abc"));
    printf("%dn", strlen_r(""));
    
    return 0;
}

輸出結果如下：

五、遞迴函數設計範例二

斐波拉契數列遞迴解法

1，1，2，3，5，8，13，21，...

程式碼如下：

#include <stdio.h>
 
int fac(int n)
{
    if( n == 1 )
    {
        return 1;
    }
    else if( n == 2 )
    {
        return 1;
    }
    else
    {
        return fac(n-1) + fac(n-2);
    }
    
    return -1;
}
 
int main()
{
    printf("%dn", fac(1));
    printf("%dn", fac(2));
    printf("%dn", fac(9));
    
    return 0;
}

輸出結果如下：

六、遞迴函數設計範例三

漢諾塔問題

將木塊藉助 B 柱由 A 柱移動到 C 柱
每次只能移動一個木塊
只能出現小木塊在大木塊之上

漢諾塔問題分解

將 n-1 個木塊藉助 C 柱由 A 柱移動到 B 柱
將最底層的唯一木塊直接移動到 C 柱
將 n-1 個木塊藉助 A 柱由 B 柱移動到 C 柱

程式碼如下：

#include <stdio.h>
 
void han_move(int n, char a, char b, char c)
{
    if( n == 1 )
    {
        printf("%c --> %cn", a, c);
    }
    else
    {
        han_move(n-1, a, c, b);
        han_move(1, a, b, c);
        han_move(n-1, b, a, c);
    }
}
 
int main()
{
    han_move(3, 'A', 'B', 'C');
    
    return 0;
}

輸出結果如下：