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.

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

2 Answers 2


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

  • \$\begingroup\$ @ialcuaz memoization is essentially to help recursion. Successive calls do not need recalculation. \$\endgroup\$
    – Caridorc
    Aug 7, 2016 at 15:23
  • 1
    \$\begingroup\$ Yes you are correct, I've posted what the final code looks like below, thanks for reminding me to use dynamic programming \$\endgroup\$
    – 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:

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.