Recursion in Python | Recursive Function, Example

Recursion in Python or any other programming language is a process in which a function calls itself one or more times in its body. It may call itself directly or indirectly.

If any function definition accomplishes the condition of recursion, we call it as recursive function.

A recursive function is a function that calls or invokes itself at least once in its body. Usually, the value returned is the return value of the function call.

A recursive function is basically a chain of function calls to the same function. Its working is just like the loop, with or without a terminating condition. It invokes itself, either directly or indirectly, via another function.

A famous example often used to describe the recursion in Python or other programming languages is the calculation of factorial (the factorial for a value of 6 is 6 * 5 * 4 * 3 * 2 * 1).

Recursion in Python is a very efficient and fundamental technique of computer programming used to resolve a specific type of complex programming problem. It is best suited when we need to call the same method repeatedly with different parameters.

Recursion provides some advantages to programmers, such as to develop the clean and short code and also helps to programmers to avoid loops.

Sometimes, the concept of recursion may be a little tricky to understand for beginners. But, the truth is that we can easily solve many complex programming problems with the help of recursion technique.

Some computational problems like towers of Hanoi, DFS, tree traversal, backtracking, etc. that other techniques can solve are better solved by recursion.

Recursion Syntax in Python


In Python, we can divide the recursion syntax into two categories:

  • Direct recursion
  • Indirect recursion

Direct recursion: It occurs when a function invokes oneself directly from inside its own body. The basic syntax to declare a recursive function in Python that calls itself directly is as:

def recursiveFunction(param):
  # function code
    recursiveFunction(param) # recursive call.

recursiveFunction(arg) # function calling with passing argument values.

In the above syntax, the recursiveFunction() is a recursive function that is invoking itself inside the function. Look at the below figure that illustrates the simple working of recursion in Python.

Syntax of recursion in Python

Let’s take a simple example based on the direct recursion.

def recursiveFunction():
    print('Hello')
    recursiveFunction() # recursive call.
recursiveFunction() # calling function.
Output:
      Hello
      Hello
      . . .

Indirect recursion: This recursion occurs when a function calls another function, which in return makes a callback to that function.


For example, when function A calls another function B and function B calls function A, we call it as indirect call. The basic syntax to declare a recursive function that invokes itself repeatedly indirect is as:

def A_function(parameter):
  # function code.
    B_function(parameter)

def B_function(parameter):
  # function code.
    A_function(parameter)

Let’s take a simple example code based on indirect recursion call.

def A_function():
    print('A')
    B_function() # recursive call.

def B_function():
    print('B')
    A_function() # recursive call.
A_function() # function calling.
Output:
       A
       B
       A
       B
       . .
       . .

As you will observe while executing the above recursive code on the console, the code is executing indefinitely. At the end, Python interpreter generates an error (RecursionError: maximum recursion depth exceeded while calling a Python object). To overcome this problem, we need to terminate the recursion. Let’s understand it.

How to stop Recursion in Python?


While defining recursive function in Python or other programming languages, it is necessary to specify a termination condition. If we set a termination condition in the recursion that means the code is properly working. If we do not set such a condition, then an infinite “function” call may occur.

For this reason, we need to specify a condition to terminate the recursion. This condition is called base case or stopping point.

Base case or terminal case is a condition that prevents infinite recursion. In the terminal case, no recursive function calls occur. Without terminal case, we can never stop the execution of recursive function.

A well-defined recursive function must satisfy two conditions that are as:

  • There must be a base case so that the function does not call itself infinite times.
  • In every call or iteration, the argument moves closer to the base case through a recurrence relation, which makes a new solution from the previous solution.

Consider the following example code given below, in which we will display a message four times using recursion method.


Example 1:

count = 0
def display():
    global count
    count += 1
    if count <= 4: # base case.
        print("Hello world")
        display() # recursive call.
display() # normal method call.
Output:
      Hello world
      Hello world
      Hello world
      Hello world

In the above program code, we have used a conditional “if statement” in the function body to check the count is less than equal to 4. This is a base condition.

As long as this conditional is true, the recursive function display() invokes itself. On each iteration, the count is increasing by 1 and function display() is called until the count is equal to four.

When the count reaches 5, the conditional statement evaluates to false. Since the base condition met, the function will not call anymore.

Example 2:

Let’s write a very simple program to print numbers from counting down from 5 to 1 based on recursion.

def countDown(num):
# Displaying the number.
    print(num, end= " ")
# Decreasing the number value by 1.
    newNum = num - 1
# Base case or stopping point.
    if newNum > 0:
        countDown(newNum)
countDown(5) # calling function.
Output:
       5 4 3 2 1

In the above program code, we have passed a number 5 as an argument while calling a function. Inside the body of function, we have used a conditional “if statement” to check the passed argument is greater than zero. This is a base condition.

As long as Python evaluates this conditional to true, the recursive function countDown() calls itself. On each iteration, the number value is decreasing by 1 and function countDown() is invoked until the number is positive.

Look at the following steps to understand recursive calls clearly.

  • countDown(5) prints 5 and calls countDown(4)
  • countDown(4) prints 4 and calls countDown(3)
  • countDown(3) prints 3 and calls countDown(2)
  • countDown(2) prints 2 and calls countDown(1)
  • countDown(1) prints 1 and calls countDown(0)

When the number reaches 0, the conditional “if statement” evaluates to false. Since the base condition met, the function is not called anymore.

Example 3:

Let’s write a program to count down numbers to 0 using recursion method.

# Program to count down numbers to 0.
def countDown(num):
    if(num < 0): # base case. Stop at 0.
        return # stop function.
    else:
        print(num, end= ' ')
        countDown(num - 1) # count down 1.
countDown(5) # calling function.
Output:
      5 4 3 2 1 0

Note: If we make a recursive call inside if block, else block contains the logic of base condition. If we make the recursive call within else block, if block should contain the logic of base condition.

Types of Recursion in Python


There are two types of recursion in Python. They are:

  • Head recursion
  • Tail recursion

Let’s understand each one by one with the help of examples.

Head Recursion

In this type of recursion, the recursive call occurs before other processing in the function. For example:

def headRec(num):
    if num == 0:
        return
    else:
        headRec(num - 1) # recursive call.
        print(num, end= ' ')
headRec(6)
Output:
      1 2 3 4 5 6

In the above program code, firstly recursive calls occur and then printing takes place. Hence, the last value of num, i.e. 1, gets displayed first. Therefore, the number prints in the order 1 to 6.

Tail Recursion

In this type of recursion, processing occurs first before the recursive call. The tail recursion acts like a loop in which the function executes all statements before making the recursive call. Let’s take an example based on it.

def tailRec(num):
    if num == 11:
        return
    else:
        print(num, end=' ')
        tailRec(num + 1)
tailRec(1)
Output:
      1 2 3 4 5 6 7 8 9 10

In this program code, first printing takes place and then the recursive call occurs. Hence, the first value of n, i.e. 1, gets displayed first on the console. Therefore, numbers print in the order 1 to 10.

Factorial Program using Recursion in Python


Here, we will learn how to compute the factorial of a number using recursive method. A factorial of a number is the product of that number and all positive integers numbers below it. We represent it as n!

For example, the factorial of a number 4 is represented by 4!. It is equal to 4 * 3 * 2 * 1, resulting in 24. The basic steps to compute the factorial of any number n, as follows:

(n) * (n – 1) * (n – 2) * (n – 3) * . . . . . * 1.

Let’s first write a program to compute the factorial of a number using for loop.

Program code:

def fact(num):
    factorial = 1
  # This statement checks whether a number is positive, negative, or zero.
    if num < 0:
        print("Invalid input!, factorial for negative numbers does not exist.")
    elif num == 0:
        print("The factorial of 0 is 1")
    else:
        for i in range(1, num + 1):
            factorial = factorial * i
        print("The factorial of", num, "is", factorial)

# Main program.
# Take the input from the user.
num = int(input('Enter a positive number you want the factorial: '))
fact(num)
Output:
       Enter a number you want the factorial: 4
       The factorial of 4 is 24

In the above program code, we have taken a number 7 as input from the user and stored it in a variable num. Then, we have called the function by passing the value of variable num.

Inside the function, we checked if the number is negative, zero or positive using if elif else statement. Inside the else block, we have used for loop and range() function to calculate the factorial of a number. Look at the following steps in the below table.

Iterationfactorial * i (returned value)
i = 11 * 1 = 1
i = 21 * 2 = 2
i = 32 * 3 = 6
i = 43 * 4 = 24

Factorial of a Number using Recursion method

Now let’s write the code to compute the factorial of a number using recursion.

Program code:

# Python program to compute the factorial of a number using recursion.
def fact(num):
    """This is a recursive function
        to find the factorial of an integer number."""
    if num == 1:
        return 1
    else:
        # Recursive calling to the function.
        return (num * fact(num - 1))

# Main program.
# Take the input from the user.
num = int(input('Enter a positive number you want the factorial: '))

# Calling function and stored the returned value in a variable result.
result = fact(num)
print('Factorial of', num, "is",result)
Output:
      Enter a positive number you want the factorial: 5
      Factorial of 5 is 120

In the above program, fact() is a recursive function, as it calls itself. When we call this function by passing positive value as argument, it will recursively call itself by decreasing the number.

Each recursive function call multiplies the number with the factorial of (number – 1) until the number is equal to 1. When the number is equal to 1, the recursion finishes. This is the base condition.

Every recursive function must have a base condition to prevent the infinite recursion. Look at the below following steps of recursive calls.

  • fact(5) – 1st call with 5
  • 5 * fact(4) – 2nd call with 4
  • 5 * 4 * fact(3) – 3rd call with 3
  • 5 * 4 * 3 * fact(2) – 4th call with 2
  • 5 * 4 * 3 * 2 * fact(1) – 5th call with 1
  • 5 * 4 * 3 * 2 * 1 – return from 5th call when number is equal to 1

At the starting, you may seem that understand the logic of recursive function is more difficult, but they become easier with practicing some programs.

Advantages of Recursion in Python


There are the following advantages of using recursion technique in Python programming. They are as:

  • Using recursion, we can break down the function into smaller sub-problems.
  • It allows us to break the complex task into simpler tasks.
  • Using recursive function makes the code appearing simple and efficient because we need to write fewer lines of code.

Disadvantages of Recursion in Python


In addition to many advantages of using recursion, there are also following disadvantages of using it in the Python programming. They are as:

  • Recursive calls consume a lot of memory and time. That’s why they are costly to use.
  • Debugging of recursive functions can be difficult.
  • Writing the logic for recursion can sometimes be difficult to understand.

In this tutorial, you have learned about recursion in Python with some important example programs. Hope that you will have understood the basic concept of recursive function and practiced all example programs.
Thanks for reading!!!

⇐ Prev Next ⇒

Please share your love