## DEV Community is a community of 867,901 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # 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 = *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()
dyna_end = timer()
print(f"Time for Dynamic = {timedelta(seconds=dyna_end-start1)}")
start2 = timer()
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

## Discussion (3) 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. Meir Gabay • Edited on

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