Complexity Analysis of Recursive Algorithms with and Without Memoization

Memoization is a computational technique for speeding up the complexity of computer algorithms. It stores the previously calculated results and invokes them later in the body of the algorithm when necessary. On the other hand, a recursive function references or calls itself; it solves a problem by solving smaller instances of the same problem. This study aimed to solve a problem by applying recursion without memoization, and recursion with memoization and then comparing their time complexities. Our methodology involved experimentation with the Fibonacci sequence using recursion with and without memoization; Programs written in Python programming language and the same programming environment were used to implement the Fibonacci sequence for some staggered integers. The time complexities of both versions of recursion were then compared. Our findings showed that in line with the analytical results, the numerical results obtained confirmed that recursion with memoization is more computationally efficient than recursion without memoization. However, the recursion with memoization had more lines of code and used more memory.