# 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.

• Broken code close vote without explanation: I have voted to leave open. Aug 7, 2016 at 12:20
• @Pimgd there was a typo in my code which I fixed last night
– ifma
Aug 7, 2016 at 22:41

### 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.

• @ialcuaz memoization is essentially to help recursion. Successive calls do not need recalculation. Aug 7, 2016 at 15:23
• Yes you are correct, I've posted what the final code looks like below, thanks for reminding me to use dynamic programming
– ifma
Aug 8, 2016 at 0:52

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: