Introduction to Recursion in Python

Want to learn all about recursion in programming? This tutorial on recursion in Python will help you get started.

Recursion is a super helpful problem-solving technique to add to your programmer’s toolbox. While initially often difficult to wrap your head around, recursion can help you come up with more elegant solutions to complex problems.

In this tutorial, we’ll take a code-first approach to learning recursion using Python. In particular, we’ll cover:

• The basics of recursion
• Recursive functions and how they work 
• Python implementation of recursive functions 
• Differences between iterative and recursive approaches to problem-solving 

Let’s get started!

What Is Recursion?

Recursion is a programming technique where a function calls itself repeatedly to solve a problem.

At its core, recursion is a problem-solving approach that involves breaking down a complex problem into smaller, identical subproblems. Essentially, it allows you to solve a problem in terms of simpler versions of itself.

So, how do we implement recursion in code? To do so, let’s understand how recursive functions work.

Understanding Recursive Functions

We define a recursive function that calls itself within its definition. Each recursive call represents a smaller or simpler version of the original problem.

To ensure that the recursion eventually terminates, recursive functions must include one or more base cases—conditions under which the function stops calling itself and returns a result.

Let’s break this down further. A recursive function consists of:

• Base Case: The base case is a condition (or conditions) that determine when the recursion should stop. When the base case is met, the function returns a result without making any further recursive calls. A base case is essential to prevent infinite recursion.
• Recursive Case: The recursive case defines how to break down the problem into smaller subproblems. In this part of the function, the function calls itself with modified inputs. Each recursive call is, therefore, a step toward reaching the base case.

Next, let’s discuss what happens when you call a recursive function.

How Recursion Works Under the Hood

When a function is called, a record of its execution context is placed on the call stack. This record includes information about the function’s arguments, local variables, and the location to return once the function finishes execution.

In the case of recursive functions, when a function calls itself, a new record is pushed onto the call stack, effectively suspending the current function’s execution. The stack allows Python to keep track of all pending function calls, including those from recursive calls.

Until the base case is reached, the recursion continues. When the base case returns a result, the function calls are resolved one by one—with each function returning its result to the previous level of the call stack. This process continues until the initial function call completes.

Implementing Recursion in Python

In this section, we’ll explore three simple examples of recursion: 

1. Calculating the factorial of a number
2. Computing Fibonacci numbers
3. Implementing binary search using recursion. 

For each example, we’ll state the problem, provide the Python recursive implementation, and then explain how the recursive implementation works.

#1. Factorial Calculation Using Recursion

Problem: Calculate the factorial of a non-negative integer n, denoted as n!. Mathematically, the factorial of a number n is the product of all positive integers from 1 to n.

The factorial calculation lends itself well to recursion, as shown:

Here’s the recursive function to calculate the factorial of a given number n:

def factorial(n):
	# Base case
    if n == 0 or n == 1:
        return 1
	# Recursive case: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

Let’s compute 5! using the factorial() function:

factorial_5 = factorial(5)
print(factorial(5))
# Output: 120

Now let’s see how the function works:

• We have a base case that checks if n is equal to 0 or 1. If the condition is met, the functions return 1. Recall that 0! is 1, and so is 1!.
• If n is greater than 1, we calculate n! by multiplying n with the factorial of n-1. This is expressed as n * factorial(n - 1).
• The function keeps making recursive calls with decreasing values of n until it reaches the base case.

#2. Fibonacci Numbers with Recursion

Problem: Find the term at the n-th index in the Fibonacci sequence. The Fibonacci sequence is defined as follows: F(0) = 0, F(1) = 1, and F(n) = F(n-1) F(n-2) for n >= 2.

def fibonacciSeq(n):
	# Base cases
    if n == 0:
        return 0
    elif n == 1:
        return 1
	# Recursion: F(n) = F(n-1)   F(n-2)
    else:
        return fibonacciSeq(n - 1)   fibonacciSeq(n - 2)

Let’s run the function:

fib_5 = fibonacciSeq(5)
print(fib_5)
# Output: 5

Here’s how the function works:

• Let’s start by discussing the base cases. If n is 0, it returns 0. And if n is 1, it returns 1. Recall F(0) = 0 and F(1) = 1.
• In the recursive case, if n is greater than 1, the function calculates F(n) by adding the F(n-1) and F(n-2) terms. This is expressed as fibonacciSeq(n - 1) fibonacciSeq(n - 2).
• The function keeps making recursive calls with decreasing values of n until it reaches the base cases.

#3. Recursive Implementation of Binary Search

Problem: Implement a binary search algorithm using recursion to find the position of a target element in a sorted list.

Here’s the recursive implementation of binary search:

def binarySearch(arr, target, low, high):
	# Base case: target not found
    if low > high:
        return -1

    mid = (low   high) // 2

	# Base case: target found
    if arr[mid] == target:
        return mid
	# Recursive case: search left or right half of the array
    elif arr[mid] > target:
        return binarySearch(arr, target, low, mid - 1)
    else:
        return binarySearch(arr, target, mid   1, high)

The function binarySearch keeps dividing the search interval in half with each recursive call until it either finds the target or determines that the target is not in the list.

Here’s a sample run of the function:

arr = [5, 8, 13, 24, 37, 49, 51, 64, 72, 88, 96]
target = 37
idx = binarySearch(arr, target, 0, len(arr)-1)
print(idx)
# Output: 4

Let’s break down what the function does:

• In the binary search recursive implementation, we have two base cases. First, if low becomes greater than high, it means the target element is not in the list. So, we return -1 to indicate that the target was not found.
• The other base case checks if the element at the middle index mid of the current search interval is equal to the target. If they match, we return the index mid, indicating that we’ve found the target.
• In the recursive case, if the middle element is greater than the target, we recursively search the left half of the array by calling binarySearch(arr, target, low, mid - 1). If the middle element is less than the target, we search for the right half by calling binarySearch(arr, target, mid 1, high).

Recursive vs. Iterative Approach

Iterative approach—using loops—is another common approach to problem solving. So, how is it different from recursion? Let’s find out.

First, we compare recursive and iterative solutions to a common problem: computing the factorial of a number.

Here’s the recursive implementation of factorial calculation:

def factorialRec(n):
	# Base case
    if n == 0 or n == 1:
        return 1
	# Recursive case: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

Because we know that the factorial of a non-negative number is the product of all numbers from 1 up to n, we can also write an iterative implementation using loops.

def factorialIter(n):
    result = 1
    for i in range(1, n   1):
        result *= i
    return result

Both these implementations give identical results.

factorial_5 = factorialRec(5)
print(factorial_5)
# Output: 120

factorial_5 = factorialIter(5)
print(factorial_0)
# Output: 120

But is an iterative approach preferred over recursion? When there’s deep recursion—with too many function calls—you may run into errors because of exceeding the recursion depth. Looping is a better option for problems whose recursive implementation requires too many function calls to reach the base case.

Let’s sum up the differences between iterative and recursive implementations:

Conclusion

In this article, we started by learning what recursion is and how to define recursive functions with base cases and recurrence relations.

We then wrote some Python code—recursive implementations of common programming problems. Finally, we learned the differences between iterative and recursive approaches and the pros and cons of each of these approaches.

Next, check out this list of Python interview questions.