Table of Contents

Refer and star the data structures & algorithms repository on Github.

I have written the python codes for the recursion problems in this tutorial. This is one part of data structures and algorithms in Python series and here you will understand the patterns needed to solve different recursion problems.

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

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
  • 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