Recursion and Memoization
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 | 0 | heading |
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. | 1 | paragraph |
#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 | 2 | code |
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 | 3 | code |
Recursion, implicit memory and Iteration | 4 | heading |
 | 5 | image |
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 | 6 | paragraph |
Promoted Promoted 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 | 7 | code |
Solving Recursion problems | 8 | heading |
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. | 9 | paragraph |
Merge Two Sorted Lists | 10 | subheading |
| Merge Two Sorted Lists | 11 | link |
 | 12 | image |
| 13 | list |
Promoted Promoted class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = 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
a.next = self.mergeTwoLists(a.next, b)
return a #return a | 14 | code |
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
head.next = a
a=a.next
elif b and not a: #if b is null, add a to head
head.next = b
b=b.next
elif a.val > b.val: #if both not null, add lowest
head.next = b
b=b.next
else:
head.next = a
a=a.next
head = head.next #make head.next as new head
return dummy.next
| 13 | code |