Skip to main content

Python Recursive Functions

Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself.

Python supports recursion.

Recursive Function in Python​

In Python, a function can call other functions, including itself.

Example of Python Recursive Function

For example, consider the following recursive function that calculates the factorial of a given number:

def factorial(x):
    if x==0 or x == 1:
        return 1
    else:
        return x * factorial(x-1)

num = 4
print(f"The factorial of {num} is {factorial(num)}")

Output:

The factorial of 4 is 24

The stack of recursive calls is as follows:

factorial(4)              # 1st call with 4
4 * factorial(3)          # 2nd call with 3
4 * 3 * factorial(2)      # 3rd call with 2
4 * 3 * 2 * factorial(1)  # 4th call with 1
4 * 3 * 2 * 1             # return from 4th call as number=1
4 * 3 * 2                 # return from 3rd call
4 * 6                     # return from 2nd call
24                        # return from 1st call

Basic structure of Recursive Function​

All recursive functions share a common structure made up of two parts: base case and recursive case.

  • The base case is the solution of the simplest possible problem. When the basic condition is satisfied, the function exits. This ensures that the function will terminate at some point.
  • The recursive case handles more complicated cases of the problem that are not easy to solve directly. This is where recursive calls are made to reduce to the base case.

Consider this example:

def factorial(x):
    if x==0 or x == 1:
        return 1
    else:
        return x * factorial(x-1)
  • the base case stops when number is 0 or 1 and returns. No other recursive calls are made.
  • the recursive case returns the number multiplied by the value returned by the recursive function call. Here the recursive call is made with argument the current number minus 1.
note

Every recursive function must have a base condition that interrupts recursion, otherwise the function will call back to infinity.

To avoid infinite recursion, Python interpreter limits the depths of recursion to 1000. You can check this limit in this way:

import sys
print(sys.getrecursionlimit())  # Prints 1000

Pros and Cons of Recursion​

Advantages​

  • Recursive functions make the code clean and elegant.
  • A complex problem can be decomposed into simpler subproblems using recursion.
  • Sequence generation is easier with recursion than with nested iteration.

Disadvantages​

  • Sometimes the logic of recursion is difficult to follow.
  • Recursive calls are expensive (inefficient) because they take up a lot of memory and time.
  • Recursive functions are more difficult to debug than iterative functions.

Table of Contents