Recursion Explained In Python

If you have been programming with Python, chances are you’ve come across the term recursion. Chances are also that you might probably find this confusing at first, not to worry, this article should clear things up for you.

Recursion is a very powerful programming concept that provides a simple, (neater in most cases), concise and efficient way of approaching and tackling different problems. Sometimes, however, it is tricky to see how a problem can be solved recursively if you do not understand the concept of recursion itself.

What is a Recursive Function?

A Recursive function is basically a function that calls itself.

You can also put:

A function that is called in its own definition is said to be recursive.

A recursive function can also be said to be a function defined in terms of itself via self-referential expression.

This means that a recursive function typically possesses the following qualities:

• A Recursive function will continue to call itself and repeat it’s self-referential act until a condition is met in order to return a result
• A typical recursive function shares a common structure that consists of two parts: (i) The recursive case: The part which breaks down the problem into simpler ones.. and (ii) The base case: The terminating condition which stops the function once it is met.

A Simple Example Of a Recursive Function

How exactly does this work in python? Well, let’s say you want to write a program to print “hello” repeatedly, a simple syntax to do this using recursion in python is:

def hello():
  print('hello')
  hello()
hello()

Sure enough, if you run the snippet above, you get “hello” printed hundreds of times until the program eventually terminates with a ‘Recursion Error’ similar to the screenshot below.

Recursion Error Explained

A recursion error happens when the program has performed a recursive function a number of times greater than than the recursion limit. In order words, a recursion error is thrown when your (recursive) function has called itself up to a pre-defined limit called the recursion limit.

By default, the recursion limit in a python program is 1000 times. i.e, a recursive function can run for a 1000 times before it throws a recursion error. The importance of the recursion limit is to help prevent your program from running for so long that it crashes your application or worse still, damages your CPU.

To check your applications recursion limit, you can run the following code snippet:

import sys
print(sys.getrecursionlimit())

Sure enough, the output is predefined as 1000.

How to modify the default recursion limit

If for example, you want to increase or decrease the predefined recursion limit in your program, you can do that by calling the sys.setrecursionlimit() method as below:

Recursion Use case: Finding the Factorial of a number

One of the most many use cases of recursion is in finding the factorial of a number. If you’re familiar with loops in python, you would traditionally do it as below:

Finding a Factorial using a for loop

number = int(input("Enter a number: "))
 
factorial = 1
 
for i in range(1, number + 1):
	factorial = factorial * i
 
print("The Factorial of ", number, " is ", factorial)

If you run this, the output you derive is:

Using a while loop, the syntax resembles:

number = int(input("Enter a number: "))
 
factorial = 1
i = 1
 
while i <= number:
	factorial = factorial * i
	i = i + 1
 
print("The factorial of ", number, " is ", factorial)

Running the program above, the output is also shown below.

However, implementing recursion, the syntax looks like:

number = int(input('Enter a number: '))

def factorial_recursion(number):
  if number == 1: #base case 
    return 1
  return number * factorial_recursion(number - 1) #recursive case

print('The Factorial of',number , 'is', factorial_recursion(number))

And we get the same output:

Advantages of recursion

1. Recursion helps to make our code easier to write.
2. Recursion helps make code easier to read and understand.
3. Another advantage of recursion is that it takes fewer lines of code to solve a problem using recursion.

Disadvantages of recursion

1. Not all problems can be solved using recursion.
2. If the base case in a recursive function is not defined, the code would run indefinitely.
3. It is relatively more difficult to debug a recursive function since the function in question is calling itself in a loop and so it hard to understand exactly which call is causing the issue.
4. Making calls to recursive functions is generally not memory efficient.

Conclusion

Recursion is a lovely concept in programming as it provides an alternative way to solve some common problems as we have seen above. What are some ways in which you use recursion? Would Do you prefer recursion over iterative programming? Let’s hear your thoughts in the comments section below.