Python Recursion: Recursive Function, Example

Table of Contents

Introduction
Recursion patterns & problems
Examples of Recursion
Recursion practice problems

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.

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)

Types of recursion

Parameterised
Functional

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

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

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,[]))

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

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

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

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

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

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

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

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