溫暖午後的金針田__孕育有趣的創新

遞迴是一個初學程式最頭痛的思考方式，運算過程中函式不斷呼叫自己，使運算的程序暫時停擺，最後才一一算出答案、合併在一起。

就好像要作青椒炒肉絲：先把各樣的食材、調味料一一切好、調味、裝進碟子，最後才一項一項合併起來。

先來看階層：n! = 1*2*3*...*(n-1)*n

以for loop實作有兩種想法：

1、bottom-up(由1一直連乘到n):

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

int main()
{
    /*Calculate 5!*/
    int n = 5,i,H=1;
    for(i=1;i<=n;i++)
        H *= i;
    printf("%d",H);/*H=120*/
    return 0;
}

2、top-down(由n一直連乘到1):

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

int main()
{
    /*Calculate 5!*/
    int n = 5,i,H=1;
    for(i=n;i>0;i--)
        H *= i;
    printf("%d",H);/*H=120*/
    return 0;
}

基本上for-loop和recursive是可以互換的，只是運算效率上for-loop通常比較好，因為recursive會使用堆疊的方式佔用空間及增加呼叫時間。

但是隨著不同的問題，for-loop和recursive誰好誰壞是不一定的，有的問題用recursive就會變得很簡單。

遞迴觀念及步驟：

1、運用function來呼叫自己，系統會自動堆疊stack，堆疊函式不用自己寫

2、先找到運算的規則，return的算式是怎麼表示

3、思考終止條件，在函式運算時，要先經過終止條件判斷，若符合條件就不再往下計算，否則會進入無限迴圈

/*我個人的經驗是，先找到規則，再思考終止條件，比較容易寫出遞迴式；

而初學者在理解別人的遞迴式時，可以運用回推思考法，從別人的終止條件往回推算，比較方便了解運作情形(畢竟我們的人腦不擅長堆疊、容易忘記剛剛算了什麼)*/

以Recursive實作：

1、bottom-up(由1一直連乘到n):

你會發現用bottom-up來寫階層會有點複雜，因為呼叫函式一定要先給最大值n是多少(要算n階層)，但是遞迴必須一直呼叫自己、並且傳入新的值進去，導致輸入需要有兩個變數。

1、先思考回傳的算式(也就是階層的運算規則)：x*(x+1)

2、若要寫成遞迴就是：return x*fact(x+1) /*遞迴的函式命名為fact*/

3、終止條件是"x+1"等於n的時候，再來思考相等時要回傳什麼數字，此時應回傳n

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

int fact(int start,int finish) /*開始連乘的數字為start，最後一個乘上數字為finish*/
{
    if(start==finish)return finish; /*終止條件*/

    int x,y;
    x = start;
    y = fact(start+1,finish);
    return (x*y); /*為了方便觀看，用x,y區分開來，這裡可以直接寫成 return (start*(fact(start+1,finish)))，那就不需要用x,y了*/
}

int main()
{
    int H=1;
    H = fact(1,5);/*5!=120*/
    printf("%d",H);
    return 0;
}

2、top-down(由n一直連乘到1):

top-down的函式相對簡單，輸入時不用兩個變數：

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

int fact(int n)
{
    if(n==1)return 1;

    int x,y;
    x = n;
    y = fact(n-1);
    return (x*y);
}

int main()
{
    int H=1;
    H = fact(5);/*5!=120*/
    printf("%d",H);
    return 0;
}