Hello, hope you are fine. Welcome to wonderful series and a new beginning of competitive programming with Python. Python is a dynamic typed language and simple to use But the community of Competitive programming with Python is a little bit small as compared to C++ and java but many of us want to do and develop codes in python to save time but hesitate to start over. From this series, we are starting competitive programming with Python. The aim of the series is to make people able to write, think and convert the logic to python code which they are afraid to do so. In this article, we will learn Recursion which is the first topic to begin competitive programming with python. Only a prerequisite is you know basic Python programming.
Table of Contents
Brief Introduction to Recursion
Recursion is simply defined as when function call itself is known as recursion but this is school definition, we are preparing for competitive coding, and interviews so we define recursion as a bigger problem that is solved by solving smaller subproblems. And for this function call itself and each time the input which is passed to function is made small. So everyone says that recursion is all about making input small but this is not the target. Input automatically becomes small by the operation we are performing. So I hope that recursion is clear to you so let's move forward.
Learn the 3 Steps to Approach Recursion
1) Base Case
when any function calls itself multiple times without any loop there must be a condition from where it gets terminated and reach out to the end or destination. The condition from where function calling terminates is termed as the base case or the base condition.
2) Induction
It is also known as recursive call where we assume the output for one input and call the function for remaining input is known as induction step.
3) Hypothesis
It is referred to as small work which we have to think over to transform input to reach out to the desired output. Basically in this step, we do some operations to reach out to the output.
We have to only master these 3 steps and you will be great at recursion. These all three steps to you will be more clear when we will start working practically on it and when you will make your hands dirty on your compiler by solving some questions.
Basic Questions on Recursion
1) Factorial Of a Number using Recursion
Problem Statement - We are given any positive integer and our target is to return the factorial of a number using Recursion.
Factorial Approach through iteration -> Factorial of any number is basically multiplication of 1 to next upcoming number till the given number.
Example
factorial of 5 = 1*2*3*4*5 = 120
Recursion Approach
First, we are given a function that takes a number as a parameter and now we have to think about how we can do a recursive call to find the factorial. So recursion question needs a little bit of observation skill so if you clearly observe the above example then the answer is the multiplication of one to its increment till the given number in an iterative way and if we say it recursive then multiplication of number to decreasing one from itself.
So what recursion says is making an input small or diving a problem into a small sub-problems so, we are given a number we can call a function each time by subtracting one from a number. Observe the below binary tree for finding factorial using recursion.
Now we can easily write a code from the above simple binary tree of recursion of factorial. so base case is where my function call will terminate.
def factorial(num):
#Base Case
if num == 1:
return 1
#Hypothesis & the recursion call
return num * factorial(num-1)
num = int(input()) #user input
print(factorial(num))
Now I hope that it is clear what we look at in recursion and how a problem is approached. Don't worry we will take a different pattern from the different data structures and solve each type of problem using recursion. Now after understanding factorial using recursion you should try a Fibonacci number of Nth term in Fibonacci series using recursion. It is very similar to the one we solved.
2) Sum of Array using Recursion
Now we are picking the recursion problem in Array. It is a very simple problem statement and I know you can solve it in a few seconds if I allow you to use loops but here we are giving an array of positive integers and we have to return the sum of all elements using recursion.
Input ~ Array and length of length in a function
Output ~ Sum of all elements
Recursive Approach
What the recursive approach says is whenever we perform the recursive call then each time we perform some operation that input becomes small or we try to make input small. Always remember that whenever we are working on sequence data types problem statements like Array, String, etc so we first focus on the first index or last index (Choice is yours).
Answer me that When we have a single element in an array then is there any need to do something? No, because a single element is itself sorted, always incrementing, always decrementing, etc. So we got the base case when the array has only a single element then it is sorted, and we can add the remaining element one by one. Now you can design a recursive tree for this problem.
What the tree says is to keep the first element of an array with you and pass the remaining array to function until it becomes an array of a single element. Now you can easily write the code. (Try writing code by yourself, it is hardly 3 lines of code).
def SumOfArray(arr, n):
if n == 1:
return arr[0]
#add first element and pass the remaining arr to function
return arr[0] + SumOfArray(arr[1:], n-1)
arr = [1,2,3,4,5]
print(SumOfArray(arr, len(arr)))
3) First Index of an element in an Array
Given an array of duplicate elements, your task is to return the first occurring index of a particular element in an array using recursion.
Input ~ Array, size of an array, search element
Output ~ First occurring index of an element in the array
Example
Inputs -> arr = [9,6,8,5,8,7] and element = 8
Output -> 2
Recursive Approach
This is also a very simple problem statement that is relatively similar to the above problem. Please try to think over it and use pen and paper to draw the recursive tree diagram of how we can solve it (Take reference to the above question). We have an array so first, our target is to check for the first element that has a lookout at the remaining elements. Our program will end when we got the first match of a required element so the base condition is simple if the first element matches the required element then terminate else again pass the remaining array to function and add one because we are moving forward.
Have you made a recursive tree? do you think we forget one condition when the element is not present in an array then how does the function call will terminate? So we have to add one more condition like if an array is empty they simply terminate with a negative one. After reading an approach and drawing a recursive tree what's there in code? I hope till now you have made it.
def FirstIndex(arr, ele, n):
if n == 0:
return -1
#if 0th index ele mathes req ele
elif arr[0] == ele:
return 0
else:
ans = FirstIndex(arr[1:], ele, n-1)
if ans == -1:
return -1
else:
return ans+1
arr = [9,6,8,5,8,7]
ele=8
print(FirstIndex(arr, ele, len(arr)))
4) Sort Array using Recursion
This is something interesting. After reading the heading of the question you might be thinking like if already there are many well-optimized sorting algorithms then why do we have to sort the array using recursion. Believe it or not, this is the most asked interview question by many MNCs.
Problem ~ Given an array of integers, the target is to sort the array without using extra array space using recursion.
Input ~ Size of an array and array elements
Output ~ Return sorted array
Recursive Approach
Think for a while that we have to make changes in the same array and sort it using recursion so how can we do that. So we learned one thing when we recursive problem on an array then first think for a single element in an array so a single element in an array is always sorted so we can implement a function to insert the remaining elements in a single-element array in a sorted form. So, let us understand better in step by step procedure.
- Pop each element from the array until the array is of a single element so this is our base case and the element we are popping stores it in a temporary variable.
- In recursion, the value in the variable is stored in stack form so the element which is removed at last will be at the top.
- Now we will insert each removed variable again into the array in the sorted form at its correct position.
- So we have a single-element array which is itself sorted and now to insert a new element we only have to check with the last element of an array that if the last element is smaller than a new element then simply push the element at the back.
- Otherwise, first, remove the last element of an array and recursively insert the new element, and after inserting the new element insert the popped element.
Now let us write the code. If now the approach is not clear then take a paper and dry run the code by taking a sample array of your choice.
def insert(arr, temp):
#if arr is empty or last element is small then new element then append
if len(arr) == 0 or arr[-1] <= temp:
arr.append(temp)
return
#else pop last element and first insert new element
val = arr.pop()
insert(arr, temp)
#insert popped element back to arr
insert(arr, val)
def sort(arr):
#base case(when 1 element then return)
if len(arr) == 1:
return
#else pop element from array
temp = arr.pop()
sort(arr) #Recursive call
insert(arr, temp) #insert one by one in sorted order
global arr
arr = [4, 2, 3, 7, 5]
sort(arr)
print(arr)
As we are suggested to make changes in the same array we declare the array as global. Remember that in different languages like C++, java, etc we pass an array by reference so changes reflect in the original array but in python, in such case, we declare the variable as global.
5) Replace Pi with 3.14 in a string
Now we have done some basic array questions on recursion So it is time to move forward with string. Now the string is also a sequence data structure which is a collection of characters. The approach which we are applying on an array will be very same while working on a string only a small work will have some modifications and you should have observation skills.
Problem statement -> Given a string, you have to change all the occurrences of pi with 3.14 and the remaining string should be as it is.
Example
INPUT = "pip"
OUTPUT = "3.14p"
Recursive approach
Think out a little bit and try to solve on paper with a recursive tree. When our program will terminate the string whose answer we know is when a string is empty there will be empty string output. So we have a function that accepts the string, we will compare the first two characters as is equal to pi so we will append 3.14 instead of it and pass a remaining string to function. And if it is not equal then we will append the first character and pass the remaining string recursively till the string is empty.
Try writing the code using the above recursive approach.
def replaceStr(st):
if st == "" or len(st) == 1: #base case
return st
if st[0:2] == "pi":
return "3.14" + replaceStr(st[2:])
else:
return st[0] + replaceStr(st[1:])
st = "pippppiiiipi"
print(replaceStr(st))
6) Count the number of zeros in a number
I am picking this question in last to give you a little bit of different taste in recursion. In this problem, we are given any number and we have to return a count of zeros present in a number.
Example
INPUT = 7080010
OUTPUT = 4
Recursive Approach
we are having a number so how can we count several zeros. So think it like a string problem like we have to return a count of characters in a string so we check every character equal to the target character. So in number, we have to check each digit equal to zero. So the question is how we access each digit. so remember of palindrome and reverse digit program where we use modulus and divide operator to decrease the number. So here also we will recursively extract the last digit of a number using modulus and check it equal to zero and recursively call the function and pass the number by removing the last digit by dividing it by zero. Observe the below recursive tree so the approach will be more clear.
Now writing code is easier and you should try it on your own using the above recursive tree.
def count_zeros(num):
if num == 0:
return num
if num % 10 == 0:
return 1 + count_zeros(num//10)
else:
return count_zeros(num//10)
n = 7080010
print(count_zeros(n))
Questions for you to Try and solve
Here are some questions similar to the above six problems we have done. I would like to request you to solve these questions and post the link to GitHub or solution in the comment box below.
A] Remove all Occurrence of char from the string
Given a string and a character you have to make a recursive function that removes each occurrence of that character from the string, and finally returns the modified string.
Example
INPUT -> string = "geeks", char = "e"
OUTPUT -> "gks"
This is a very simple program and the logic is exactly similar to what we have done to replace the Pi question.
B] Count Distinct number of substring
Given a string, you need to find the number of substrings of string that contain at least one occurrence of substring "beauty" followed by at least one occurrence of substring "brain".
Example
INPUT -> string = "beautybrainy"
OUTPUT -> 2
Explanation
2 substrings contain both "beauty" and "brain" as substrings "beautybrain" and "beautybrainy". Hence the answer is 2
C] Insert Star between Identical Pairs
Given a string with repeated characters, we have to insert a star i.e. "*" between pair of adjacent identical characters using recursion.
Example-1
INPUT = "aabb"
OUTPUT = "a*ab*b
Example-2
INPUT = "xxxy"
OUTPUT = "x*x*xy"
I want this problem you should try with pen and paper. Think over the approach how can we make it and use the key points which we have studied like when a string is empty they simply return is our base case else check for the first index element and do the small work needed to achieve a solution.
Recursive Approach ~ I am only explaining the recursive approach behind it, code you have to submit in the comment section below. So, the base case is a simple call till the string does not become empty. Now in function, you have to accept a string and a character(initially it will be an empty string) and you have to check that the first character of the string matches the accepted character. If true then add first char, then start, and then recursive call passing remaining string and current character. If false then simply add the first character and recursive call.
Conclusion
Congratulations! If you have followed the article till here then I am sure that the cap of your head is now open and able to think recursive approach. Listen that this is only a strategy with recursion to start over competitive programming with Python. In the next part of recursion, we will increase the level of questions and will practice how a well recursive binary tree is formed and how to think over different questions which generate different solutions or number of possible cases like printing all subsets of string, finding all permutation with changing the letter case, Tower of Hanoi, and many different problems.
Thank You for your time! 😊