This article was published as a part of the Data Science Blogathon
Introduction:
Hello Readers, hope all of you are doing great. In this article, we will be covering all the basics needed for a beginner to start with recursion in python.
What is Recursion?
In many programs, you must have implemented a function that calls/invokes some other function. For example :
def A(): b()
Here we see that the function ‘A’ calls the function ‘B’
So a basic example of recursion would be the case, when the function would call itself, in place of some other function.
A function is said to be a recursive function if it calls itself.
They are of two types: indirect and direct recursion.
When a function calls itself directly, from within its body, it is direct recursion. Example :
def rec(): rec()
On the other hand, when a function calls some other function, which in turn calls its caller function again, is called indirect recursion. Example :
def A(): B() def B(): A()
Base Case for Recursion in Python
Let us consider the following code :
def fun1():
print("Hello function 2")
fun2()
def fun2():
print("Hello function 1")
fun1()
Can you predict what shall be the output?
Yes, you guessed it right, the code will print endlessly !!
This is because the functions will keep on calling each other endlessly.
But does this mean, that the entire memory will be used up in the process? NO, python will return an error to prevent that and stop right there.
The error will be something like:
RuntimeError: maximum recursion depth1 exceeded...
So clearly, when using recursion, we must write a sensible code, that instructs the compiler, when to stop the process, this is where Base Case comes into play.
A Base Case is a case, whose result is known or predetermined, without any recursive calling. you will have a better understanding of a base case when u see an example.
Example to calculate the sum of ‘n’ numbers using recursion in Python
Shown below, is the code, to calculate e the sum of first ‘n’ numbers, using recursion.
def rec(n):
if n==1 :
return 1 # This is a Base Case
else:
return (n+rec(n-1))
last = int(input("Enter the upper limit"))
s = rec(last)
print("Sum of series from 1 to ", last," is :", s)
The output of the above code came out to be :
Enter the upper limit 4 Sum of series from 1 to 4 is :10
Let us understand how the code works :
In the ‘main’ block, the rec function is called, with the value that the user entered, which in this case was 4, i.e., rec(4) was invoked initially.
Now the control, shifts to line 1, where code of rec() begins. The variable ‘n’ is assigned value 4.
As n==1 turns out to be false, it goes to the else part.
Line 5 calculates return value as n+rec(n-1), as n=4, it becomes 4 + rec(3)
So rec is again called with value 3. So this goes on and on until the value of n reduces to 1, and the base case is hit, and 1 is returned. No variable s gets the value 10 returned., which then prints the sum of the series in the next line.
Recursive Definition
A Recursive definition is a definition that is made in terms of the smaller version of itself. Consider the following example :
xn = x*x*x*x…n times
Now it can be represented in terms of recursive definition as follows :
xn = x*(xn-1) for n > 1 (This is the recursive definition)
=x (for n=1) or 1 (for n=0)
Writing a recursive function
Before you start writing a recursive function, you must know, that every recursive function must have at least two cases. They are :
1) The Base Case, that we know how to solve, which leads to the recursion to end. In other words, it is the case whose value is pre-known.
2) The Recursive Case is the more general case of the problem we are trying to solve, using a recursive call to the same function.
For example, Power (x,n) = x * Power(x, n-1)
Here , the base case would be :
Power (x,n) = 1 when n=0, or x (when n=1)
NOTE : The base case in a recursive function, MUST BE REACHABLE!
Computing GCD Recursively
We can efficiently compute the gcd of two numbers using the concept of recursion. Note that this holds for positive p and q.
If p>q,
the gcd of p and q is the same as the gcd of p and p%q. That is our python code to compute gcd.
def gcd(p,q):
if q== 0:
return p
return gcd (q,p%q)
Here, the base case is when q is 0, with gcd (p,0) = p. To see that the reduction step converges to the base case, observe that the second input strictly decreases in each recursive call since p%q <q. If p<q the first recursive call switches arguments.
This recursive approach to calculate the GCD of two numbers is called Euclid’s Algorithm.
Recursion versus Iteration
A simple yet crisp difference between the two would be :
In iteration, the block of code is executed repeatedly, using the same memory space. That is, the memory space, once allocated, is used for each pass of the loop.
On the other hand, in recursion, since it involves a function call at each step, fresh memory is allocated for each recursive call. For this reason, because of the function call overheads, the recursive function runs slower than its iterative counterpart.
Disadvantages of recursion
Recursion, along with it, also brings some of its own disadvantages. Some are :
- It is slower as compared to iteration.
- Logical but difficult to find the error, if any exists.
- Requires extra storage space this is because, for every recursive call, separate memory is allocated for the variables.
- Recursive functions often throw a Stack Overflow Exception when processing or operations are too large.
Ending Notes
That ends your journey through recursion, a programming technique in which a function calls itself. Recursion, as you saw, is rightfully isn’t appropriate for every task, and is not always an alternative to iteration. But some programming problems need it. In those situations, it’s a great technique to have at your disposal.
About the Author :
Hey there, I am Pinak Datta, currently, a second-year student, pursuing Computer Science Engineering from Kalinga Institute of Industrial Technology, Bhubaneswar. My interests include Web development, Competitive Coding, and a bit of Machine Learning too. Please feel free to connect with me through my socials. I always love to have a chat with similarly minded people.
Hi, I'm Pinak Datta, currently pursuing my B.Tech in Computer Science and Engineering from Kalinga Institute of Industrial Technology. I'm in my third year of study and I've always had a keen interest in technical writing and software development. I love to develop programs and scripts using Python and have worked on several projects in this language.
Apart from my academic pursuits, I've also participated in various hackathons and coding competitions. These experiences have allowed me to showcase my creativity and problem-solving abilities in the field of computer science.
