C之遞歸函數(shù)（四十一）

        我們今天來講下遞歸，遞歸是一種數(shù)學(xué)上分而自治的思想。遞歸是需要邊界條件的，當(dāng)邊界條件不滿足時(shí)，遞歸將繼續(xù)進(jìn)行；當(dāng)邊界條件滿足時(shí)，遞歸停止。遞歸是將大型復(fù)雜問題轉(zhuǎn)化為與原問題相同但規(guī)模較小的問題進(jìn)行處理。

        函數(shù)體內(nèi)部可以調(diào)用自己，它的函數(shù)體中存在自我調(diào)用的函數(shù)；遞歸函數(shù)是遞歸的數(shù)學(xué)思想在程序設(shè)計(jì)中的應(yīng)用，遞歸函數(shù)必須有出口，函數(shù)的無(wú)限遞歸將導(dǎo)致程序棧溢出而崩潰。遞歸模型我們一般會(huì)表示成下面這樣

        我們下面用遞歸的方法編寫函數(shù)求字符串長(zhǎng)度，思想就是下面這樣

        具體代碼如下

#include <stdio.h>

int strlen_r(const char* s)
{
    if( *s )
    {
        return 1 + strlen_r(s+1);
    }
    else
    {
        return 0;
    }
}

int main()
{
    printf("%d\n", strlen_r("abc"));
    printf("%d\n", strlen_r(""));
    
    return 0;
}

        我們看看編譯結(jié)果

        結(jié)果如我們所想。下面我們來看看怎樣用遞歸來實(shí)現(xiàn)斐波拉契數(shù)列：1，1，2，3，5，8，13，21，... 后面的每個(gè)數(shù)就是前面的兩個(gè)數(shù)字和，用公式表示出來就是這樣

        我們來看看程序是怎樣的

#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("%d\n", fac(1));
    printf("%d\n", fac(2));
    printf("%d\n", fac(9));
    
    return 0;
}

        前面兩個(gè)肯定打印出來的都是1，第3個(gè)打印出來的是34,。我們來看看編譯結(jié)果

        我們下來再來看看遞歸在漢諾塔問題中的應(yīng)用，如下所示，將木塊借助 B 柱由 A 柱移動(dòng)到 C 柱；每次只能移動(dòng)一個(gè)木塊；只能出現(xiàn)小木塊在大木塊之上；

        我們來分解下這個(gè)問題，將 n - 1 個(gè)木塊借助 C 柱由 A 柱移動(dòng)到 B 柱；將最底層的唯一木塊直接移動(dòng)到 C 柱；將 n - 1 個(gè)木塊借助 A 柱由 B 柱移動(dòng)到 C 柱。我們來看看程序是怎么實(shí)現(xiàn)的

#include <stdio.h>

int han_move(int n, char a, char b, char c)
{
    if( n == 1 )
    {
        printf("%c ==> %c\n", 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;
}

        我們看看編譯結(jié)果

        我們看到已經(jīng)正確實(shí)現(xiàn)了這個(gè)問題的解法。通過對(duì)遞歸的學(xué)習(xí)，總結(jié)如下：1、遞歸是一種將問題分而自治的思想；2、用遞歸解決問題首先要建立遞歸的模型；3、遞歸解法必須要有邊界條件，否則無(wú)解！

        歡迎大家一起來學(xué)習(xí) C 語(yǔ)言，可以加我QQ：243343083。