Recursion

Hello Everyone 🙋🏻‍♂️,

In this article, we will take a look at recursion in python. The purpose of this article is not about analyzing the complexity or which approach is better (iterative or recursive). As many searches, sort, and traversal programs use recursion as their solution, it becomes important to understand the basics of recursion prior to getting into the DSA.

Recursion as the name says is a way in which a function recursively calls itself directly or indirectly. While you intend to write recursion, you have to be very careful as the function calls can get into infinite loops. However, there is a default upper limit set for the number of recursion calls, beyond which the program runs into stack overflow or runtime error. A recursion algorithm has two cases, the recursive case, and the base case. Recursion is terminated once the base case is recognized. Generally, the base case output is already known so we can directly return the value when this case is encountered.

With recursion, you can break complex problems into similar smaller ones. Also, the code is more readable than the iterative approach. Recursion is slower than iteration as it has to maintain the stack and uses more memory.

The greet() function calls itself recursively, if you call the function and run this code, it will result in an infinite loop that would print "hello" as output as there is no base case in the function to terminate the recursion. However, in python, you can encounter the RecursionError once the upper limit of the recursion call is reached.

You can get or set the recursion limit in python using the sys module, to do so execute the following code in your python terminal,

import sys

# fetch the recursion upper limit
sys.getrecursionlimit()
# ouput: 1000

# if you intend to change the upper limit, you can do so by executing
sys.setrecursionlimit(200)

That's it for the basic understanding of recursion.

---

Now, let's see an example for finding the factorial of a number using recursion.

Factorial of a number is a product of all positive numbers smaller than or equal to the number. It is represented by using exclamation after the number. Also, remember that the Factorial of 0 is 1 (0!=1).

def factorial(number):
    '''
    The base case here is when the number becomes 0, we already know 0! = 1
    we can directly return 1 once the base case is reached.
    '''
    if number == 0:
        return 1
    return number * factorial(number-1)

factorial(4)

Visualize the factorial recursion code below by clicking the next option

You can observe, the factorial function calls itself with a number decremented by 1, once it reaches the base-case the recursion stops and starts returning the value for each function call until it reaches the actual call factorial(4) and returns the value 24.

I hope this article, helps you understand the basics of recursion. As an exercise, you can try implementing the fibonacci series using python and visualize the code on pythontutor.

Thanks for reading 🙇🏻‍♂️

references

hackerearth.com/practice/basic-programming/.. everythingcomputerscience.com/discrete_math..