Calculating the result of a recurrence function

The recurrence function is defined as follows:

• \$f(0) = 1\$

• \$f(1) = 1\$

• \$f(2n) = f(n)\$

• \$f(2n+1) = f(n) + f(n-1)\$

I was tasked to calculate the recurrence of a very large number, \$n = 66666666666666\$, using C++. As you can clearly see, the 3rd line applies for even inputs, and the 4th line for odd inputs. If this isn't clear consider the following derivation for \$f(10)\$:

\$f(10) = f(5) = f(2) + f(1) = f(1) + f(1) = 1 + 1 = 2\$

long long int function(long long int x) {
  if (x == 0 || x == 1) 
      return 1; 

  long long int result = 0;

  if (x % 2 != 0) {
      result += function((x-1)/2) + function((x/2)-1);
  } else {
      result += function(x/2);
  }

  return result;
}

The runtime of this implementation is very large (almost 30 seconds to finish). Clearly this is because recursion is very expensive. My runtime limit is 1.0s, at most. Therefore I think an iterative approach would work wonders.

This is the result of running time ./my_program:

real  0m29.893s
user  0m29.809s
sys   0m0.075s

I am wondering if there are other approaches, besides translating it to an iterative version, which would be suitable for this problem in particular. I would also be grateful if anyone has any pointers about my code/approach.

Avoid the result variable

The result variable is only ever incremented once and then returned. You can simplify by returning directly:

if (x % 2 != 0) { 
  return function((x-1)/2) + function((x/2)-1); 
} else { 
  return function(x/2);
}

Eliminating the variable should also speed-up the program if the compiler did not optimize it out already.

Memoization

Memoization essentially stores already computed values for later re-use trading space for run-time. Memoization has already been implemented in C++ so you can just make use of it.

StackExchange Code Review Q#138044, answer score: 7