Recursion and Memoization

Topic: Algorithms

The recursive call to a function is one of the methods to solve a problem that is made of many sub-problems. In recursion, the main idea is to find a base sub-problem and use it recursively. E.g Find factorial of 6. We calculate 6! by multiplying 6 with 5!. Calculate 5! by multiplying 5 with 4!. So recursively we can solve factorial of n by calculating n * func(n-1). But while running this program the computer still needs to calculate every factorial. To calculate 6! it will still need to calculate 4! even though we already calculated 4! while calculating 5!. This is time-consuming so we use small memory to store previous calculations. Before doing new calculations first we check if the calculation is already in memory. If it is not, we calculate the result from memory. This is called Memoization. This method is pretty popular for solving Dynamic Programming and Backtracking Problems.

Fibonacci Series with Recursion and Memoization


The Fibonacci Series is a classic problem in programming. It can be solved using recursion and memoization. Following is the python code to solve Fibonacci Series for n using recursion and memoization.

#Fibonnaci Series with recursion def fib(n): if n==0: return 0 if n == 1: return 1 return fib(n-1) + fib(n-2) n=6 while n: print(fib(n)) #print sequence 1,1,2,3,5,8 n-=1
def fib(n, memo): #with Memo and recursion if n==0: return 0 if n == 1: return 1 if n not in memo: #if n is already solved return solved value else calculate and add to memo memo[n] = fib(n-1, memo) + fib(n-2, memo) return memo[n] n=6 memo={} while n: print(fib(n,memo)) #print sequence 1,1,2,3,5,8 n-=1

Recursion, implicit memory and Iteration

Recursion and implicit memory.

In the above both codes we use recursion. In the first code, it seems we don’t require extra memory. But that is not true. The computer requires to store partial results in the stack before calculating sub-problems. After calculation, it pops out partial results from the stack and computes results. For Eg for n = 3, the computer pushes fib(3), then it pushes fib(2) and calculates fib(1) which is 1. Then it pops fib(2) from the stack and calculates. Finally, pop fib(3), calculate, and return the result. It does the same even if we use memoization. It is not space-efficient that is why we use iteration. All the recursion problems can be solved as iteration problems. It might get complicated but could be more efficient than recursion. Following is the iteration code of the same Fibonacci Series



def fib(n, memo): #with Memo and iteration if n==0: return 0 memo[0]=0 #base cases memo[1]=1 i=2 while i<=n: if i not in memo: memo[i] = memo[i-1] + memo[i-2] i+=1 return memo[n] n=6 memo={} while n: print(fib(n,memo)) #print sequence 1,1,2,3,5,8 n-=1

Solving Recursion problems


Recursion is a very popular and easiest technique to solve Linked List and Binary Tree problems. Most of the recursion problem can be solved in O(n) time and space complexity where n is the number of nodes. Following are few examples.


Merge Two Sorted Lists

Given a two sorted linked list merge it into one linked list.
  • Here we have two linked lists a and b. We want to use recursion.
  • We keep updating a and at the end, we will return the head of a.
  • But before solving any recursion problems we need to check base condition.
  • In this case base condition is check for b. If b is null then return a. If b is less than a then swap a and b.
  • Then we use recursion to check the next nodes of a.


class ListNode: def __init__(self, val=0, next=None): self.val = val = next def mergeTwoLists(a: ListNode, b: ListNode) -> ListNode: if not a or b and a.val > b.val: #check if a or b is null and b is smaller than a a, b = b, a #swap a and b if a: #if a is not null go to next node of a = self.mergeTwoLists(, b) return a #return a
With Iteration def mergeTwoLists(a: ListNode, b: ListNode) -> ListNode: head = dummy = ListNode(0) #use dummy node amd head, keep adding lowest number to head while a or b: if a and not b: #if a is null, add b to head = a elif b and not a: #if b is null, add a to head = b elif a.val > b.val: #if both not null, add lowest = b else: = a head = #make as new head return