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.

💡 Introduction to recursion video

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

• Problem statement link

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

• Problem statement link

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

• Problem statement link

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

• Problem Statement

• 💡 Video explaination

• Python Implementation

Sudoko Solver

• Problem Statement

• 💡 Video explaination

• Python Implementation

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

• Leetcode subsets

• Print Subsequence if sum == x

• Print First Subsequence if sum == x

• Count total subsequence where sum == x

• Leetcode combination sum I

• Leetcode combination sum II

• Subset Sum 1: Given a list of of N integers, prints sums of all subsets in it in increasing order

• Leetcode subsets II

• Print all permutations of an array