C語言遞回函式分析-有解無憂

遞回，是一種數學思想

遞回是一種數學上分而自治的思想，遞回需要有邊界條件：
當邊界條件不滿足時，遞回繼續進行；當邊界條件滿足時，遞回停止，
遞回將大型復雜問題轉化為與原問題相同但規模較小的問題進行處理，

遞回函式，函式體內部可以呼叫自己
（1）函式體中存在自我呼叫的函式
（2）遞回函式是遞回的數學思想在程式設計中的應用
（3）遞回函式必須有遞回出口
（4）函式的無限遞回將導致程式堆疊溢位而崩潰

遞回模型一般表示法：
在這里插入圖片描述

##用遞回的方法撰寫函式來求字串的長度，即遞回版本的strlen函式
例如字串：“HELLO”，
s指標指向字符H，s+1指標指向ELLO字串，那么只要計算出s+1子串的長度再進行加1，即字符H，連續遞回呼叫自己，就可以算出整體的長度了，
在這里插入圖片描述

#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;
}

列印出了3和0.

還有經典的斐波拉契數列
1 ，1，2，3，5，8，13，21，34…
斐波拉契數列遞回解法
在這里插入圖片描述

#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;
}

漢諾塔問題
在這里插入圖片描述

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

在這里插入圖片描述

#include <stdio.h>

//n個木塊，a，b，c三根柱子
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;
}

得出的結果如下，按照程式給出的結果可以解決這個問題，
在這里插入圖片描述

小結：
遞回是一種將問題分而自治的思想，用遞回解決問題首先要建立遞回的模，型遞回解法必須要有邊界條件，否則無解，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/281353.html

標籤：其他

上一篇：Winegrape資料集下載

下一篇：小程式云開發-云存盤