Recursion In Python

You might have studied functions in python. You might also have used for loops and while loops to perform a task repetitively while programming in Python. In this article, we will discuss recursion and recursive functions in Python.

What Is Recursion?

Recursion is a mathematical concept in which we define something in terms of itself. 

For instance, we can define the sum of the first ten natural numbers as the sum of the first nine natural numbers added to the tenth number. 

Similarly, we can define the sum of the first nine natural numbers as the sum of the first eight natural numbers added to the ninth natural number.

Here, you can see that we are breaking the problem of the first ten natural numbers into smaller problems like finding the sum of the first 9 numbers, then finding the sum of the first 8 numbers, and so on. In this way, we will come to a position where we have to find the sum of the first natural number i.e. 1 itself. After that, we will have to perform only the atomic addition instead of worrying about the count of natural numbers we are finding the sum of. 

When To Use Recursion In Python?

As seen above, we can use recursion whenever we can break a problem into a similar but smaller problem.  The most common problems where we use recursion are:

1. Binary tree traversal problems
2. Finding the factorial of a number
3. Tower of Hanoi problem
4. Finding Fibonacci series

How To Use Recursion In Python?

In programming, if a function calls itself, we say that it is a recursive function i.e. it works on the concept of recursion. You can use recursion in python to implement the solution for any problem that can be reduced to a similar but smaller problem. 

For instance, let us try to find the sum of the first 10 natural numbers. For that, let us define a function sumOfNumbers() that receives an input number N and returns the sum of numbers from 1 to N.

• To calculate the sum of first 10 natural numbers i.e.  sumOfNumbers(10), we will find the sum of the first 9 natural numbers i.e. sumOfNumbers(9) and will add 10 to it.
• Similarly, to find the sum of first 9 natural numbers i.e.  sumOfNumbers(9), we will find the sum of the first 8 natural numbers i.e. sumOfNumbers(8) and will add 9 to it.
• Again, to find the sum of the first 8 natural numbers i.e.  sumOfNumbers(8), we will find the sum of the first 7 natural numbers i.e. sumOfNumbers(7) and will add 8 to it.
• After that, to find the sum of the first 7 natural numbers i.e.  sumOfNumbers(7), we will find the sum of the first 6 natural numbers i.e. sumOfNumbers(6) and will add 7 to it.
• In this way, we will reach a position when we will have to calculate the sum of the first natural number i.e. sumOfNumbers(1). Here, we can simply return 1. This is also called the base case of the recursion as the problem cannot be reduced further into smaller problems. 

We can implement the above algorithm as follows.

def sumOfNumbers(N):
    if N == 1:
        return N
    else:
        return N + sumOfNumbers(N - 1)


input_number = 10
output = sumOfNumbers(input_number)
print("Sum of first {} natural numbers is {}".format(input_number, output))
input_number = 20
output = sumOfNumbers(input_number)
print("Sum of first {} natural numbers is {}".format(input_number, output))

Output:

Sum of first 10 natural numbers is 55
Sum of first 20 natural numbers is 210

While using recursion, we must specify the base case. Otherwise, the program will continue its execution continuously and run into RecursionError. This is due to the fact that the maximum number of recursive calls a function can make is capped at 1000 in Python. If any function makes more than 1000 recursive calls, a RecursionError exception will occur.

Conclusion

In this article, we have discussed recursion in python. We have also implemented a program to find the sum of the first 10 natural numbers in Python. To learn more about functions, you can read this article on closures in python.