Refer and star the data structures & algorithms repository on Github.
What is recursion
Recursion is a function that calls itself till a base condition is met.
Recursion patterns and problems
Print from 1 to n using recursion
def f(n):
if n < 1:
return
f(n-1)
print(n)
n = 5
f(n)
Print from n to 1 using recursion
n = 5
def f(n):
if n < 1:
return
print(n)
f(n-1)
f(n)
💡 Video explaination
Types of recursion
Parameterised
Functional
💡 Video explaination
Using parameterized recursion, print the sum of the first n natural numbers in python
n = 6
def f(n, sum=0):
if n < 1:
return sum
return f(n-1,sum+n)
print(f(n))
Using functional recursion, print the sum of the first n natural numbers in python
def f(n):
if n <= 1:
return n
return n + f(n-1)
print(f(n))
Reverse an array of size n using parameterized recursion in python
arr = [1,2,3,4,5,6]
def f(arr, left, right):
if left >= right:
# print(arr)
return arr
arr[left],arr[right] = arr[right],arr[left]
return f(arr,left+1, right-1)
print(f(arr,0,len(arr)-1))
Reverse an array of size n using functional recursion in python
def f(arr,pointer):
if pointer >= len(arr) -1 // 2:
return arr
arr[pointer], arr[len(arr)-1-pointer] = arr[len(arr)-1-pointer], arr[pointer]
return f(arr,pointer+1)
print(f(arr,0))
Check whether a string is a palindrome or not in python
string = "NITIN"
def f(string, pointer):
if pointer > (len(string) - 1) // 2:
return True
if string[pointer] != string[len(string)-1-pointer]:
return False
return f(string,pointer+1)
print(f(string,0))
💡 Video explaination
Multiple Recursion Calls: Fibonacci Number in Python
n = 5
def f(n):
if n <= 1:
return n
return f(n-1)+f(n-2)
print(f(n))
💡 Video explaination
Recursion on subsequences (Subset)
- Leetcode problem statement: https://leetcode.com/problems/subsets/
arr = [3,1,2]
def f(arr,pointer=0, sub_arr=[], final_arr = []):
if pointer >= len(arr):
# print(sub_arr)
final_arr.append(sub_arr)
return sub_arr
f(arr,pointer+1,sub_arr+[arr[pointer]], final_arr) #Pick
f(arr,pointer+1,sub_arr, final_arr) #Not Pick
return final_arr
print(f(arr,0,[]))
💡 Video explaination
Print Subsequence if sum == x
arr = [3,1,2]
sum = 3
def f(arr,sum,pointer=0,sub_arr=[],sub_arr_sum=0,final_arr=[]):
if pointer >= len(arr):
if sub_arr_sum == sum:
# print(sub_arr)
final_arr.append(sub_arr)
return
f(arr,sum,pointer+1,sub_arr,sub_arr_sum,final_arr) # Not Pick
f(arr,sum, pointer+1, sub_arr+[arr[pointer]], sub_arr_sum + arr[pointer], final_arr)
return final_arr
print(f(arr,sum))
Print First Subsequence if sum == x
arr = [3,1,2]
sum = 3
def f(arr,sum,pointer=0,sub_arr=[],sub_arr_sum=0):
if pointer >= len(arr):
if sub_arr_sum == sum:
# print(sub_arr)
return sub_arr
return
left = f(arr,sum,pointer+1,sub_arr,sub_arr_sum)
right = f(arr,sum,pointer+1,sub_arr+[arr[pointer]],sub_arr_sum+arr[pointer])
if left is not None: return left
if right is not None: return right
return
print(f(arr,sum))
Count total subsequence where sum == x
arr = [3,1,2]
sum = 3
def f(arr, sum, pointer=0, sub_arr_sum=0):
if pointer >= len(arr):
if sub_arr_sum == sum:
return 1
return 0
l = f(arr, sum, pointer+1, sub_arr_sum)
r = f(arr, sum, pointer+1, sub_arr_sum+arr[pointer])
return l+r
print(f(arr,sum))
💡 Video explaination
Leetcode combination sum I
arr = [1,2,3]
target = 3
def f(arr,target,pointer=0,sub_arr=[], sub_arr_sum=0, final_arr=[]):
if pointer >= len(arr):
if target == 0:
final_arr.append(sub_arr)
# print(sub_arr, sub_arr_sum, target)
return
if(target >= arr[pointer]):
f(arr,target-arr[pointer], pointer,sub_arr+[arr[pointer]],sub_arr_sum+arr[pointer], final_arr)
f(arr,target,pointer+1,sub_arr,sub_arr_sum, final_arr)
return final_arr
print(f(arr,target))
💡 Video explaination
Leetcode: Combination SUM II
arr = [10,1,2,7,6,1,5]
arr.sort()
target = 8
def f(arr,target,pointer=0,sub_arr=[],final_arr=[]):
if target == 0:
# print(sub_arr)
final_arr.append(sub_arr)
return final_arr
for i in range(pointer,len(arr)):
if i != pointer and arr[i] == arr[i-1]: continue
if arr[i] > target: break
f(arr,target-arr[i],i+1,sub_arr + [arr[i]],final_arr)
return final_arr
print(f(arr,target))
💡 Video explaination
Given a list of N integers, prints sums of all subsets in it in increasing order.
Input = [2,3]
output = [0,2,3,5]
arr = [5,2,1]
def f(arr,pointer=0,sub_arr_sum=0,final_arr=[]):
if pointer >= len(arr):
final_arr.append(sub_arr_sum)
return final_arr
f(arr,pointer+1,sub_arr_sum+arr[pointer],final_arr)
f(arr,pointer+1,sub_arr_sum,final_arr)
return final_arr
print(sorted(f(arr)))
💡 Video explaination
Leetcode Subsets II
arr = [1,2,2]
def f(arr,pointer=0,sub_arr=[],final_arr=[]):
final_arr.append(sub_arr)
for i in range(pointer,len(arr)):
if i != pointer and arr[i] == arr[i-1]: continue
f(arr,i+1,sub_arr + [arr[i]],final_arr)
return final_arr
print(f(arr))
💡 Video explaination
Print all permutations of an array in python - Approach 1
arr = [1,2,3]
freq = [False] * len(arr)
def f(arr,freq,pointer=0,sub_arr=[],final_arr=[]):
if len(sub_arr) == len(arr):
final_arr.append(sub_arr)
# print(sub_arr)
return
for i in range(0,len(arr)):
if not freq[i]:
freq[i] = True
f(arr,freq,i+1,sub_arr+[arr[i]],final_arr)
freq[i] = False
return final_arr
print(f(arr,freq))
💡 Video explaination
Print all permutations of an array in python - Approach 2
Example: [1,2,3]: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
arr = [1,2,3]
def f(arr,pointer=0,final_arr=[]):
if pointer >= len(arr):
final_arr.append(arr.copy())
# print(arr)
return
for i in range(pointer,len(arr)):
arr[pointer],arr[i] = arr[i],arr[pointer]
f(arr,pointer+1,final_arr)
arr[pointer],arr[i] = arr[i],arr[pointer]
return final_arr
print(f(arr))
💡 Video explaination
Examples of Recursion
Common problems in recursion
N-Queens Problem
Sudoko Solver
Recursion practice problems
Print from 1 to n using recursion
Print from n to 1 using recursion
Using parameterised print sum of first n natural numbers
Using functional, print sum of first n natural numbers
Reverse an array of size n using parameterised recursion
Reverse an array of size n using functional recursion
Check whether string is palindrome or not
Fibonacci Number
Print Subsequence if sum == x
Print First Subsequence if sum == x
Count total subsequence where sum == x
Subset Sum 1: Given a list of of N integers, prints sums of all subsets in it in increasing order
Print all permutations of an array