快捷導(dǎo)航

C語(yǔ)言深入分析遞歸函數(shù)的實(shí)現(xiàn)

更新時(shí)間：2022年04月15日 17:25:15 作者：清風(fēng)自在流水潺潺

遞歸（recursive）函數(shù)是“自己調(diào)用自己”的函數(shù)，無(wú)論是采用直接或間接調(diào)用方式。間接遞歸意味著函數(shù)調(diào)用另一個(gè)函數(shù)（然后可能又調(diào)用第三個(gè)函數(shù)等），最后又調(diào)用第一個(gè)函數(shù)。因?yàn)楹瘮?shù)不可以一直不停地調(diào)用自己，所以遞歸函數(shù)一定具備結(jié)束條件

一、遞歸的數(shù)學(xué)思想

遞歸是一種數(shù)學(xué)上分而自治的思想

遞歸需要有邊界條件

當(dāng)邊界條件不滿足時(shí)，遞歸繼續(xù)進(jìn)行
當(dāng)邊界條件滿足時(shí)，遞歸停止

遞歸將大型復(fù)雜問(wèn)題轉(zhuǎn)化為與原問(wèn)題相同但規(guī)模較小的問(wèn)題進(jìn)行處理。

二、遞歸函數(shù)

函數(shù)體內(nèi)部可以調(diào)用自己

遞歸函數(shù)

函數(shù)體中存在自我調(diào)用的函數(shù)

遞歸函數(shù)是遞歸的數(shù)學(xué)思想在程序設(shè)計(jì)中的應(yīng)用

遞歸函數(shù)必須有遞歸出口
函數(shù)的無(wú)限遞歸將導(dǎo)致程序棧溢出而崩潰

三、遞歸函數(shù)設(shè)計(jì)技巧

遞歸模型的一般表示法

四、遞歸函數(shù)設(shè)計(jì)示例一

用遞歸的方法編寫函數(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é)果如下：

五、遞歸函數(shù)設(shè)計(jì)示例二

斐波拉契數(shù)列遞歸解法

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

輸出結(jié)果如下：

六、遞歸函數(shù)設(shè)計(jì)示例三

漢諾塔問(wèn)題

將木塊借助 B 柱由 A 柱移動(dòng)到 C 柱
每次只能移動(dòng)一個(gè)木塊
只能出現(xiàn)小木塊在大木塊之上

漢諾塔問(wèn)題分解

將 n-1 個(gè)木塊借助 C 柱由 A 柱移動(dòng)到 B 柱
將最底層的唯一木塊直接移動(dòng)到 C 柱
將 n-1 個(gè)木塊借助 A 柱由 B 柱移動(dòng)到 C 柱

代碼如下：

#include <stdio.h>
 
void 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é)果如下：