Making recursions faster, 7 million times...

The title of the post is not misguiding at all. Take a look at the time-taken numbers for the two recursion codes, and the huge difference in them -

Time taken by conventional recursion = 720000000µs (12 mins)
Time taken by improved recursion = 92µs
Faster by = 720000000/92

The 'improved' recursion code is faster by well over 7 million times. Read on to understand how it is done.

Most of the programmers are familiar with recursive code, and almost all of us have solved recursive problems like Fibonacci series or Factorial during our CS courses. We know that if try higher numbers, the code crashes with StackOverflowError.

Dynamic programming or DP as it is popularly known is a blessing for many problems requiring either recursive or iterative algorithms. In short, dynamic programming is an approach of solving complex problems by breaking them into several smaller sub-problems, where the sub-problems are overlapping sub-problems. It can make lot of recursive problems much more efficient. Dynamic programming approach is similar to recursive programming, however in dynamic programming the intermediate results are cached/stored for future calls.

If we consider recursive programing for Fibonacci series, computing the nth number depends on the previous n-1 numbers and each call results in two recursive calls. Thus, the time complexity is –

T(n) = T(n-1) + T(n-2) = O(2ⁿ)

In other words, as we increase the Fibonacci number, the time taken to compute that Fibonacci number increases exponentially. On the other hand, if we use Dynamic programming for the Fibonacci number, since the earlier results are already cached, we simply have complexity as –

Time Complexity = O(n)
Extra Space = O(n)

In fact, it is fairly easy to reduce additional space for Fibonacci number by just storing previous two results instead of storing all the previous results.

It means that Dynamic programming can drastically reduce the time taken to compute solutions that require several recursive/iterative calls. I've written this small piece of Python code that computes Fibonacci number using recursion as well as Dynamic programming. See the execution results posted below the code to know respective time taken while computing the 45th Fibonacci number. You can try this code with different numbers on your own computer as well, and see how you can make your recursions million times faster.

from timeit import default_timer as timer
from datetime import timedelta

fibo_cache = [0]*200

def recursive_fibonacci(num):
    if num in (0, 1):
        return num

    return recursive_fibonacci(num-1) + recursive_fibonacci(num-2)


def dynamic_fibonacci(num):
    if num in (0, 1):
        return num
    elif 0 != fibo_cache[num]:
        return fibo_cache[num]

    fibo_cache[num] = dynamic_fibonacci(num-1) + dynamic_fibonacci(num-2)
    return fibo_cache[num]


if __name__ == '__main__':

    fibo_num = 45  # change as needed
    start1 = timer()
    print(f"Dynamic fibonacci answer = {dynamic_fibonacci(fibo_num)}")
    dyna_end = timer()
    print(f"Time for Dynamic = {timedelta(seconds=dyna_end-start1)}")
    start2 = timer()
    print(f"Recursive fibonacci answer = {recursive_fibonacci(fibo_num)}")
    rec_end = timer()
    print(f"Time for Recursive = {timedelta(seconds=rec_end-start2)}")

This code is hosted on GitHub here - fibo.py

---

Cover image gratitude: http://xkcdsw.com/1105

Comments

[Juan Carlos]

Theres a big bug there!, you need 2 "start" variables, otherwise the time is wrong.

Heres my Nim solution:

import times

var fibo_cache = newSeq[int](200)

func recursive_fibonacci(num: int): int =
  if num in {0, 1}: return num
  result = recursive_fibonacci(num - 1) + recursive_fibonacci(num - 2)

proc dynamic_fibonacci(num: int): int =
  if num in {0, 1}: return num
  elif 0 != fibo_cache[num]: return fibo_cache[num]
  fibo_cache[num] = dynamic_fibonacci(num - 1) + dynamic_fibonacci(num - 2)
  result = fibo_cache[num]

when isMainModule:
  const fibo_num = 45  # change as needed
  let start = now()
  echo "Dynamic fibonacci answer = ", dynamic_fibonacci(fibo_num)
  echo "Time for Dynamic = ", now() - start
  let start2 = now()
  echo "Recursive fibonacci answer = ", recursive_fibonacci(fibo_num)
  echo "Time for Recursive = ", now() - start2

I use let start2 = now() to fix the bug.

Also dynamic_fibonacci() has Side-Effects but recursive_fibonacci() does not.

[Manish]

Fixed, thanks :-)

[Meir Gabay]

I'm wondering if this can be implemented by providing a number and an empty list, and return a list with all the Fibonacci numbers, according to the given number