在C++中優化遞歸

Question

我有一個遞歸函數。我想優化它少於10秒。更高的內存使用率不是問題。

目前，在Linux上花費大約85秒，在Mac上花費了三倍。

我無法理解我能以何種方式繼續？

這裏是代碼：

using namespace std; 

double get_wall_time(){ 
    struct timeval time; 
    if (gettimeofday(&time,NULL)){ 
     // Handle error 
     return 0; 
    } 
    return (double)time.tv_sec + (double)time.tv_usec * .000001; 
} 

int fun(long long n) { 

    if (n < 0) { 
     cout << "Please enter valid number"; 
     return 0; 
    } 

    else if (n == 0 || n == 1) 
     return 1; 

    else if (n % 2 == 0) 
     return fun(n/2); 

    else if (n % 2 == 1) 
     return fun(n/2) + fun(n/2 - 1); 

    else 
     return 0; 
} 

int main() { 
    double begin = get_wall_time(); 
    cout << fun(123456789) << std::endl; 
    double end = get_wall_time(); 
    cout << "Time elapsed : " << double(end - begin); 
    return 0; 
} 

編輯：
如果n爲偶數，則返回f(n/2)
如果n是奇數，返回f(n/2)+f(n/2-1)

Answer 1

我會用std::mapmemoize的結果，如所以：

std::map<long long, int>fun_results; 
int fun(long long n) { 
    try { 
     return fun_results.at(n); 
    } catch(const std::out_of_range&) { 

     if (n < 0) { 
      cout << "Please enter valid number"; 
      return 0; 
     } 

     else if (n == 0 || n == 1) 
      return fun_results[n] = 1; 

     else if (n % 2 == 0) 
      return fun_results[n] = fun(n/2); 

     else if (n % 2 == 1) 
      return fun_results[n] = fun(n/2) + fun(n/2 - 1); 

     else 
      return 0; 
    } 
} 

結果：

1332403 
Time elapsed : 0.000710011