5.遞迴

• 遞迴的定義：一個函數或副程式呼叫自己反覆執行，就稱為遞迴

• 範例1：數學上的階乘 n!=n*(n-1)*(n-2)*.....*1

• =n*(n-1)!

• =n*(n-1)*(n-2)!

• 注意：1!=1 0!=1

• 以程式碼實作階乘函數

int fact(int n){

if(n==0)

return 1;

else

return n*fact(n-1);

}

• 範例2：費伯那序列

• n為正整數

• n=0時，Fn=0

• n=1時，Fn=1

• n>1時，Fn=Fn-1+Fn-2

• 以程式碼實作費伯那序列

int fib(int n){

if(n==0) return 0;

if(n==1)

return 1;

else

return fib(n-1)+fib(n-2);

}

作業：

使用遞迴方式寫出計算M的N次方數字為何

請交CPP檔