題組內容

四、有一費氏(Fibonacci)數學函式如下：（3 題，每題 5 分，共 15 分）
F(n) = F(n – 1) + F(n – 2)，n ＞ 0
F(1) = 1、F(0) = 0

(一)請以遞迴(Recursive)方式寫出上列函式程式碼。

詳解 (共 2 筆)

詳解 提供者：polar33794

int F0=0;
int F1=1;
void main()
{
  int n=3;
  int Fn=0;
  Fn=F(n,Fn);
  printf("F%d=%d",n,Fn);
}
    int F(int n,int Fn)
    {
        if((n<2)&&(n>-1))//n=0或是1
        {
            return n;//回傳F0="0"(n=0)或是F1="1"(n=1)
        }
        else if(n>=2)
        {
            Fn=F(n-1,Fn)+F(n-2,Fn);
            return Fn;
        }
        else
        {
            printf("n小於0!");
            return -99;
        }
    }

詳解 提供者：hchungw
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

測試範例
for i in range(10):
    print(f"F({i}) = {fibonacci(i)}")

 

解釋

  1. 基本情況 (Base Cases)：

    • 當 n 等於 0 時，返回 0。這是費氏數列的第一個值。
    • 當 n 等於 1 時，返回 1。這是費氏數列的第二個值。

  2. 遞迴步驟 (Recursive Step)：

    • 當 n 大於 1 時，函式調用自身來計算前兩個費氏數列的值 (F(n-1) 和 F(n-2)) 並將其相加。

這個函式將根據給定的 n 值遞迴計算費氏數列，並返回對應的費氏數列值。注意，由於遞迴方法會重複計算相同的子問題，因此對於較大的 n 值，性能可能較差。在實際應用中，可以考慮使用動態規劃或其他優化技術來提高效率。