Promoted
Promoted

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.

1paragraph
#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
2code
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
3code

Recursion, implicit memory and Iteration

5image

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

6paragraph

Promoted
Promoted

def fib(n, memo): #with Memo and iteration if n==0: return 0 memo=0 #base cases memo=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
7code

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.

9paragraph

Merge Two Sorted Lists

12image
• 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.
13list

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
14code