在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