用遞歸計算函數F（n）

Question

閱讀主題，我不知道它在說什麼： 函數F（n）在非負整數上確定如下： F（0）= 1; F（1）= 1; F（2n）= f（n）; F（2n + 1）= F（n）+ F（n + 1） 通過遞歸計算F（n）。 和我的代碼：

#include<iostream.h> 
double TINH_F(int n) 
{ 
    if(n == 0) 
    { 
     return 0; 
    } 
    if(n == 1) 
    { 
     return 1; 
    } 

    return (F(n+1) - F(2*n+1)); 
} 

Answer 1

這顯然是不正確的。遞歸函數調用本身，包括停止條件：

#include<iostream.h> 
double TINH_F(int n) 
{ 
    if(n == 0) 
    { 
     return 0; 
    } 
    if(n == 1) 
    { 
     return 1; 
    } 

    // Note the function name change 
    return (TINH_F(n+1) - TINH_F(2*n+1)); 
} 

什麼你應該做的功能，如果傳入的是一個負整數？遞歸是否仍然有效？或者你應該拋出一個異常來向呼叫者表明合同已經中斷？

Answer 2

int f(int n) 
{ 
    if (n<0) return -1; // check if n is positive 
    if (n<=1) return 1; // we can catch the first two cases in a single condition 

    int half = n/2; 

    if (n % 2 == 0) return f(half); // if n is even 
    else return f(half) + f(half+1); // if n is odd 
} 

Answer 3

你的最後一種情況下說

• F（N）= F（N + 1）+ F（2 * N + 1），對於所有的n> 1

如果你仔細閱讀定義，這種情況在任何地方都沒有提及。

我相信你被參數的命名所欺騙 - 你需要四種情況。

讓我們來分析一下：

• F（0）= 1（或0 - 你的定義說：1，但代碼表示，0 ...）
• F（1）= 1
• F（2N）= F（n）的
• F（2N + 1）= F（N）+ F（N + 1）

前兩種情況是微不足道的。

第三種情況說如果參數 - 我們稱之爲m - 是偶數，則結果爲F(m/2)。

第四種情況說如果參數m是奇數，則結果爲F(m/2) + F(m/2 + 1)。
（確認留作練習算術。）

在C++：

unsigned int TINH_F(unsigned int n) 
{ 
    if(n == 0) 
    { 
     return 1; 
    } 
    else if(n == 1) 
    { 
     return 1; 
    } 
    else if (n % 2 == 0) 
    { 
     return TINH_F(n/2); 
    } 
    else 
    { 
     return TINH_F(n/2) + TINH_F(n/2 + 1); 
    } 
}