Recursive Algorithms: Cycle of Redundant Calculations

Recursive algorithms are powerful tools in programming, allowing us to elegantly solve complex problems by breaking them down into simpler, more manageable subproblems. However, one common challenge that arises with recursive functions is the tendency to recalculate the same values multiple times, leading to inefficiencies. In this article, we'll explore this issue and propose a novel approach to optimize recursive algorithms in Python.

# Here is the most common recursive function in Python:
# It gives the sequence in Fibonacci series.
In [6]: def fibo(n):
   ...:     if n <= 2:
   ...:         return 1
   ...:     return fibo(n-1) + fibo(n-2)
In [13]: fibo(8)
Out[13]: 21
In [16]: fibo(9)
Out[16]: 34        

Well nothing is wrong here, this work perfectly fine.

What is we pass 50 or something bigger...

In [16]: fibo(50)
# It will take forever... :)        

There lies a great problem in this approach. Lets take an example of getting the sequence in 8.

When we pass 8, the if statement will be checked, obviously the code from the return stament will be execute. Now from there a recursive call is made with n-1 and n-2, In first case recursive call with value 7 and 6, from those another recursive call with 6, 5 and 5, 4 another recursive call will with values, 5,4, 4,3 , 4,3,3,2................ The list goes on and on. Imagine we pass 50, we will need a paper and pen to trace the call, thats like millions or trillions. Most of the calculation will be redundant. So lets solve this..

# recursive with a memo
In [26]: def fibo(n, memo={}):
    ...:     if n in memo:
    ...:         return memo[n]
    ...:     if n <= 2:
    ...:         return 1
    ...:     result = fibo(n-1, memo) + fibo(n-2, memo)
    ...:     memo[n] = result
    ...:     return result        

Here, we are first returning the value from memo, if it exists the reset is same expect the part where we store the result in memo.

Well this is my approach, feel free to suggest your idea and view.

Try the fibo of any number with the memo and without memo you will be surprised with result.