Python Recursion

Recursion is one of the most interesting yet important concepts of any programming language. If you want to be a good programmer or data scientist, then you should better have a very good and deep understanding of recursion. Recursion functions are used everywhere in programming, from searching and sorting to other important concepts. Even in every interview, you can expect a question from recursion.

In this tutorial, we will understand recursion and how to implement it using Python. We will also understand it with an example to make it clearer.

What is Recursion?

Recursion can be understood as a concept in which a function calls itself. We are already familiar with the condition, where a function calls another function but in recursion, a function calls itself directly or indirectly. The function which implements recursion is known as a recursive function.

It’s very important to be very careful while writing a recursive code because if not written correctly, it can be very hard to debug it and it can also go in an infinite loop, which is not good for any program. But writing the code correctly and efficiently can be very useful.

Each recursive function has two features:

1. Base case: It is the desired condition which should be reached for the recursive function to stop. This is the ultimate goal to achieve in a recursive function. It is mandatory to have a base case in a recursive function. Otherwise, the function would not be able to know when to stop and come out of the function. Hence can go into an infinite loop. Without a base case, the default depth for recursion is 1000. After that the compiler will show RecursionError.
2. Recursive case: It is the case where the recursive functions keep going into another recursive function until they reach the base case. It is the middle stage of a recursive function.

Syntax

 def recursive_fun ( ):
          #recursive function calls
          recursive_fun ( )
recursive_fun( )

One thing to understand is that any problem that can be solved using a recursive function can also be solved using an iterative function with the help of a loop. But there are times when we should use loops and there are times when we should use a recursive function. Recursion divides a bigger problem into smaller functional problems and then solves them.

Let’s understand with an example.

Example1: Finding the factorial of a number.

Factorial of n = n * (n-1) * (n-2) * (n-3) *…..* 3 * 2 * 1

Iterative method

Code

def fact(n): 
    x = 1     
    for i in range(2, n+1):
        x *= i
    return x
 
num = fact(5);
print(num)

Output:

120

Explanation

In the above code, we have used the iterative approach to solve the problem. We have called the function named fact () once and inside that function we have used a loop for calculating the factorial. Once the loop reaches the boundary condition, we come out of the loop and return the factorial value. The factorial value will be stored in the variable named num and then we will print it.

Recursive method

Code

def fact(n):
    # Base Case
    if n==0:
        return 1
    # Recursive Case
    return n*fact(n-1)


fact_num = fact(5)
print(fact_num)

Output:

120

Explanation

In the above code, we have used the recursive approach to solve the problem. We have called the function named fact with a value of 5. In this function, we have written our base case (if n is equal to zero, then return one) and the recursive case. If the argument satisfies the base condition, we will come out of the recursive function (go to the recursive function with an argument as n-1). Otherwise, we will enter into another recursive function with a different argument. This process will continue until we reach the base case.

What are Direct and Indirect Recursion?

Direct recursion is the default recursion method where a function invokes itself. Indirect recursion is when a function calls another function and then eventually gets invoked. Let’s say function A calls Function A then it is a direct recursion while if function A calls function B and function B calls function C and function C calls function A then it is indirect recursion because eventually function A gets called recursively.

Syntax:

Direct Recursion

def fun ( ):
    #recursive call
     fun ( )


#function call
fun( )

Indirect Recursion

def funA( ):
     #calls another function
     funB( )


def funB( ):
     #calls another function
     funC( )


def funC( ):
      #calls again the first function
      funA( )


funA( )

Advantage of Recursion

• Recursion helps in making the code more clean and readable.
• In recursion, we can divide a bigger problem into smaller ones and then solve them efficiently.
• It is easier to generate sequences using recursion than using nested iteration.

Disadvantage of Recursion

• In recursion, a lot of time and memory are needed which makes it an expensive function.
• It can easily get out of hand with just simple coding mistakes. Hence it’s very peculiar.
• It is hard to debug a recursive code.
• Sometimes it can be hard to understand a recursive function's logic.