Calculating the result of a recurrence function

Question

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.

Answer 1

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.

Answer 2

I don't have the c++ file on me, but if anyone is interested in what the final program looks like, here is what it essentially looks like in pseudocode. Thanks @Caridorc for suggesting a memoization procedure. It is easily translatable to c++:

Function f(n):
  if n is either of the two base cases, return 1 

  let M be the memoization table

  if n is cached: 
    return M[n]

  if n is not cached:
    if n is even:
      M[n] = f(n/2);   

    if n is odd:
      M[n] = f((n-1)/2) + f((n/2)-1);

  return M[n]

I screenshot-ed the new execution time: