Recursion in Python
Recursion generally means finding a solution to a problem by repeatedly solving the simpler versions of the same problem. A similar meaning applies to recursions in programming languages, where we use the concepts with functions. In the article, we will learn recursion in Python with some examples, along with the advantages and disadvantages of recursion.
What is Recursion in Python?
In Python, recursion is the process of a function calling itself directly or indirectly. This is a way to get to the solution of a problem by breaking it into smaller and simpler steps. The syntax of recursion in Python is:
def func_name(parameters): <- - - - - - --
……….. |
……….. |
……….. |
: |
func_name(updated parameters) - - - -
Wondering how many times the function will call itself? Will it go to infinite steps?
Similar to the case of loops, where we give a condition that needs to be satisfied for the next iteration to occur. Here also, we give a base condition. But the difference is that when this condition is satisfied, the function stops calling itself. This is because if the base condition is satisfied, then it means the elementary step of the function is reached.
Knowing this information, let us see an example for a clear picture about recursion.
Example of finding the sum of numbers using recursion:
def sum(n):
if(n==0):
return 0
return n+sum(n-1)
sum(5)
Output:
We can see that we can do recursion in a simple way with a few lines of code. Let us see some more outputs.
Example of finding the sum of numbers using recursion:
sum(10) sum(0)
Output:
55
0
How does Recursion work in Python?
In the function in the above example, we are calculating the sum of all natural numbers till ‘n’. Since we are calculating the sum of only natural numbers, we stop counting all numbers from 1 to n. So, we should stop when the number reaches 0 and therefore, the base case is ‘n==0’. And in this case, the value returned is 0.
Let us see step by step process:
1. First, sum(5) is called
2. 5 is not equal to 0. So, the 5+sum(5-1) executes. That is, sum(4) is called now.
3. Now, n=4 and n is not equal to 0. So, the statement 4+sum(4-1) executes. This calls the function again.
4. The value of n is 3 and it is not equal to 0. So, 3+sum(3-1) executes. The function is called with argument 2.
5. 2 is not equal to 0. The second return statement 2+sum(2-1) executes. This calls sum(1)
6. Again, 1 is not equal to 0. So, this executes 1+sum(1-1). The function sum is called with n=0.
7. 0 is equal to 0. The base condition is satisfied now. This returns 0.
8. Not the whole process gets reversed.
9. sum(0)=0 => 1+sum(1-1)=1+sum(0)=1+0=1. This value is equal to sum(1).
10. sum(1)=1 => 2+sum(2-1)=2+sum(1)=2+1=3, which is equal to sum(2).
11. sum(2)=3 => 3+sum(3-1)=3+sum(2)=3+3=6. This value is equal to sum(3).
12. sum(3)=6=> 4+sum(4-1)=4+sum(3)=4+6=10, which is equal to sum(4).
13. sum(4)=10=> 5+sum(5-1)=5+sum(4)=5+10=15. This value is equal to sum(5).
14. Therefore, the output of sum(5) is 15.
Uses of Recursion in Python
Though it is possible to write a program without using recursion, there are cases where the recursion becomes self-important. One of such examples includes the situations where we need previous values like generating fibonacci series. Recursion is also used while using nonlinear data structures like a linked list, tree, etc. to do operations like traversal, insertion, etc.
Its limitations include more memory requirements, time consumption, and the possibility of awkwardness. Besides these, it is still used due to the facilitation of readable code and the necessity according to the problem.
Problem of Infinite Recursion in Python
Let us see the output of the above function when we give a negative number as an input.
Example of finding the sum of numbers using recursion when the input is negative:
def sum(n):
if(n==0):
return 0
return n+sum(n-1)
sum(-3)
Output:
<ipython-input-6-df2835a027b6> in <module>
4 return n+sum(n-1)
5
—-> 6 sum(-3)<ipython-input-6-df2835a027b6> in sum(n)
2 if(n==0):
3 return 0
—-> 4 return n+sum(n-1)
5
6 sum(-3)… last 1 frames repeated, from the frame below …<ipython-input-6-df2835a027b6> in sum(n)
2 if(n==0):
3 return 0
—-> 4 return n+sum(n-1)
5
6 sum(-3)RecursionError: maximum recursion depth exceeded in comparison
We can see that we got an error. This is because we are updating the value of ‘n’ by decreasing it by 1. Since the number is -3, on decreasing the number further, the condition ‘n==0’ is never reached. This leads to infinite calls of the function and we get an error.
We can get void of the error by giving a more appropriate base condition or checking the value of the ‘n’ before calling the function. We will see both these cases in the below two examples.
We can give the base condition as n<=0 rather than n==0. This will also deal with the negative numbers. For example,
Example of finding the sum of numbers using recursion with a different base condition:
def sum(n):
if(n<=0):
return 0
return n+sum(n-1)
print(sum(6))
sum(-5)
Output:
21
0
We can see that, we got a proper output for a positive value and the negative value of ‘n’ did not give any error.
Another way to do this is to use conditional statements before calling the function.
Example of finding the sum of numbers using recursion called after checking the input value:
def sum(n):
if(n==0):
return 0
return n+sum(n-1)
n=8
if(n<0):
print('Number is negative')
else:
print(sum(n))
Output:
Example of finding the sum of numbers using recursion called after checking the input value:
def sum(n):
if(n==0):
return 0
return n+sum(n-1)
n=-10
if(n<0):
print('Number is negative')
else:
print(sum(n))
Output:
In this way also we can prevent the occurrence of infinite recursions. We can adopt any of these two ways depending on the convenience and necessity.
Tail Recursion in Python
Tail recursion is another form of recursion, where the function calls itself at the end. Using the tail recursion, we do not keep the track of the previous state or value. Remember the working of a normal recursive function, where we had to go back to the previous calls and add the values till we reached the first call.
Here we do not need to do this. Let us discuss more with the example of the sum() function.
Example of finding the sum of numbers using tail recursion:
def sum(n,last=0):
if(n<=0):
return last
return sum(n-1,n+last)
sum(3)
Output:
Here, the recursive call is the last statement inside the function that is executed. Also, observe that we are passing one more parameter along with n and this is the value that is returned on reaching the base condition. And while calling the function, we are updating the last value with the sum. Because of this, we do not need to keep track of the previous calls.
Let us see the process happening above in the following steps:
1. sum(3) is called. n=3 and last =0. 3 is not less than or equal to 0. So, the statement sum(3-1, 3+last) executes. This calls sum(2,3+0)=>sum(2,3)
2. Now n=2 and last=3. 2 is not equal to 0. This call the function again => sum(2-1, 2+last) => sum(1,2+3)=> sum(1,5).
3. The value of n is 1 and last is 5. 1 is not equal to 0. So, the function is called => sum(1-1, 1+last) => sum(0,1+5)=> sum(0,6).
4. Now n=0 and last=6. 0 is equal to 0. This returns the last.
5. Since the value of last is 6, we get the output as 6.
In these steps observe that the features of the tail-recursive function (i.e., the function is called at the end and there is no need to stack previous calls) are satisfied. Also, notice that this requires a lesser number of steps. But it needs additional memory to store the value(s) to be returned, here the variable ‘last’.
Advantages of Recursion in Python
1. The recursive function makes the code look cleaner.
2. It gives ease to code as it involves breaking the problem into smaller chunks.
3. Using recursion, it is easier to generate the sequences compared to iteration.
Disadvantages of using recursion in Python:
1. Recursion is expensive in both memory and time. We can see that it needs a lot of memory to store the previous values and also it involves a lot of steps that take time.
2. Though it looks simple, it is sometimes hard to make the algorithms using recursion.
3. Recursive functions are hard to debug. Even a single line of code may lead to an error or unexpected output.
Interview Questions on Recursion in Python
Let us see some more coding examples on recursions in the section.
Q1. Write a program to print factorial of a value using recursion.
Ans. Below is the example of finding factorial using recursion in Python:
def fact(n):
if(n<0):
print('Invalid number')
return 0
elif(n==0):
return 1
return n*fact(n-1)
fact(6)
Output:
Q2. Write a program to print ‘n’ Fibonacci numbers.
Ans. Below is the example of printing Fibonacci using Python recursion:
fibs=[0,1]
a=0
b=1
def fib(n):
global a
global b
if n==2:
print(fibs)
return
temp=a
a=b
b=b+temp
fibs.append(b)
fib(n-1)
fib(10)
Output:
Q3. Write a function to reverse a string recursively.
Ans. Below is the example of reversing a string using Python recursion:
def rev(s):
if len(s)==0:
return s
return rev(s[1:])+s[0]
rev('Python')
Output:
Q4. Write the function that takes input from the user till he/she enters 0 and returns the sum of all the numbers entered. Use tail recursion.
Ans. We can take some as the default argument that is returned when the base condition, that is input =0, is reached.
Example of summing numbers entered recursively in Python:
def sum_ip(sum=0):
n=int(input('Enter a number to add or else give input as 0 to stop inputting: '))
if(n==0):
return sum
return sum_ip(n+sum)
sum_ip()
Output:
Enter a number to add or else give input as 0 to stop inputting: 12
Enter a number to add or else give input as 0 to stop inputting: -3
Enter a number to add or else give input as 0 to stop inputting: 9
Enter a number to add or else give input as 0 to stop inputting: 5
Enter a number to add or else give input as 0 to stop inputting: 0
28
Q5. Write a function that randomly chooses a value between 1 and 10. And takes the inputs from the user till the number is guessed. Also, tell the user if the guessed number is lesser or more than the number to be guessed.
Ans. We can generate a random number using a random module. And use conditionals to check if the number is equal to the input or not.
Example of a number guessing program using recursion:
import random
def guess(n):
inp=int(input('Enter a number between 1 and 10: '))
if(n==inp):
print('Congratulation! You guessed it correctly.')
return
elif(n>inp):
print('Enter a bigger number')
guess(n)
else:
print('Enter a lesser number')
guess(n)
guess(random.randint(1,11))
Output:
Enter a lesser number
Enter a number between 1 and 10: 3
Congratulation! You guessed it correctly.
Quiz on Recursion in Python
Conclusion
In this article, we learned to write a recursive function and its working. We learned about tail recursion and also the pros and cons of recursion. Finally, we saw some coding examples on the recursion.
Hope you enjoyed reading this article. Happy learning!
check your questions 10 and 15. they don’t have an initial function call. at least, I didn’t see it on my android phone.