Skip to content
CodeMDD.io | Coding Tutorials

Python Tutorial: Achieving 'ab' Equality Using Recursion

[

Recursion in Python: An Introduction

If you’re familiar with functions in Python, then you know that it’s quite common for one function to call another. In Python, it’s also possible for a function to call itself! A function that calls itself is said to be recursive, and the technique of employing a recursive function is called recursion.

It may seem peculiar for a function to call itself, but many types of programming problems are best expressed recursively. When you bump up against such a problem, recursion is an indispensable tool for you to have in your toolkit.

By the end of this tutorial, you’ll understand:

  • What it means for a function to call itself recursively
  • How the design of Python functions supports recursion
  • What factors to consider when choosing whether or not to solve a problem recursively
  • How to implement a recursive function in Python

Then you’ll study several Python programming problems that use recursion and contrast the recursive solution with a comparable non-recursive one.

What Is Recursion?

The word recursion comes from the Latin word recurrere, meaning to run or hasten back, return, revert, or recur. Here are some online definitions of recursion:

  • Dictionary.com: The act or process of returning or running back
  • Wiktionary: The act of defining an object (usually a function) in terms of that object itself
  • The Free Dictionary: A method of defining a sequence of objects, such as an expression, function, or set, where some number of initial objects are given and each successive object is defined in terms of the preceding objects

A recursive definition is one in which the defined term appears in the definition itself. Self-referential situations often crop up in real life, even if they aren’t immediately recognizable as such.

In programming, recursion has a very precise meaning. It refers to a coding technique in which a function calls itself.

Why Use Recursion? Most programming problems are solvable without recursion. So, strictly speaking, recursion usually isn’t necessary.

However, some situations particularly lend themselves to recursion. When a problem can be divided into smaller, identical subproblems, recursion can be an efficient and elegant solution.

Recursion is often used for tasks such as traversing data structures, generating permutations or combinations, solving puzzles or games, and searching or sorting algorithms.

In addition to solving problems recursively, understanding recursion can enhance your understanding of algorithms and data structures. Many classic algorithms, such as quicksort and the Tower of Hanoi, rely on recursion.

Now let’s dive into the specifics of how recursion works in Python and explore some practical examples.

Recursion in Python Python’s design and syntax make it easy to implement recursive functions. In fact, Python has no limit on the depth of recursion. However, there are practical limits imposed by the resources of your computer.

Python uses a stack to keep track of function calls. Each time a function calls itself, a new stack frame is created. This stack frame contains the local variables and parameters for that particular invocation of the function. When a function finishes executing, its stack frame is popped off the stack, and control returns to the previous stack frame.

The following steps outline the process of using recursion in Python:

  1. The function checks for a base case, a condition under which the function will not call itself recursively. This base case is necessary to prevent infinite recursion.
  2. If the base case is not met, the function calls itself with a modified input. This is known as the recursive case.
  3. The function continues to call itself recursively until the base case is met.

Get Started: Count Down to Zero Let’s start with a simple example to illustrate how recursion works. Consider the task of counting down from a given number to zero.

def count_down(n):
    if n == 0:  # base case
        print("Blastoff!")
    else:  # recursive case
        print(n)
        count_down(n - 1)  # recursive call

In this example, the function count_down takes an integer n as input. If n is equal to zero, the function prints “Blastoff!” and returns. Otherwise, it prints the value of n and calls itself with n - 1 as the new input.

Let’s call the function with an initial value of 5:

count_down(5)

The output will be:

5
4
3
2
1
Blastoff!

As you can see, the function counts down from 5 to 0 by calling itself recursively.

This simple example demonstrates the three steps of recursion:

  1. The base case is when n is 0, i.e., the countdown has reached zero.
  2. The recursive case is when n is not 0, i.e., the countdown is still in progress.
  3. The function calls itself with n - 1 as the new input, moving closer to the base case.

Calculate Factorial Now let’s explore a classic example of using recursion: calculating the factorial of a number.

The factorial of a non-negative integer n is the product of all positive integers less than or equal to n. It is denoted by n!.

def factorial(n):
    if n == 0:  # base case
        return 1
    else:  # recursive case
        return n * factorial(n - 1)  # recursive call

In this example, the function factorial takes an integer n as input. If n is equal to zero, the function returns 1, indicating the factorial of 0. Otherwise, it returns the product of n and the factorial of n - 1, calculated by calling itself recursively.

Let’s calculate the factorial of 5:

result = factorial(5)
print(result)

The output will be:

120

The factorial of 5 is 120.

Define a Python Factorial Function The factorial function can also be implemented iteratively using a loop. Here’s an equivalent non-recursive version of the factorial function:

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

This iterative version performs the same calculation as the recursive version but uses a loop instead of recursion.

Speed Comparison of Factorial Implementations Now let’s compare the performance of the recursive and iterative factorial implementations.

import time


start_time = time.time()
recursive_result = factorial(100)
recursive_time = time.time() - start_time


start_time = time.time()
iterative_result = factorial_iterative(100)
iterative_time = time.time() - start_time


print(f"Recursive result: {recursive_result}")
print(f"Recursive time: {recursive_time} seconds")
print(f"Iterative result: {iterative_result}")
print(f"Iterative time: {iterative_time} seconds")

The output will be:

Recursive result: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Recursive time: 0.00012373924255371094 seconds
Iterative result: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Iterative time: 2.1696090698242188e-05 seconds

As you can see, both implementations produce the same result. However, the recursive implementation takes slightly longer to execute compared to the iterative implementation.

Traverse a Nested List Recursion is also useful for tasks such as traversing nested data structures, like lists. Let’s explore how recursion can be used to traverse a nested list.

A nested list is a list that contains other lists as its elements. Here’s an example of a nested list:

nested_list = [1, [2, [3, [4, 5], 6], 7], 8]

To traverse a nested list means to access each element in the list, including the elements of any nested lists. Recursion allows you to write a compact and flexible traversal function.

Traverse a Nested List Recursively Here’s an example of a recursive function that traverses a nested list and prints its elements:

def traverse_list(nested_list):
    for element in nested_list:
        if isinstance(element, list):  # check if element is a list
            traverse_list(element)  # recursively call traverse_list
        else:
            print(element)


traverse_list(nested_list)

The output will be:

1
2
3
4
5
6
7
8

As you can see, the function correctly traverses the nested list, printing each element in order.

Traverse a Nested List Non-Recursively Now let’s compare the recursive solution with a non-recursive one. Here’s an equivalent non-recursive function that traverses a nested list:

def traverse_list(nested_list):
    stack = [nested_list]  # create a stack to keep track of elements
    while stack:
        element = stack.pop()
        if isinstance(element, list):
            stack.extend(element)  # add elements to the stack
        else:
            print(element)


traverse_list(nested_list)

The output will be the same:

1
2
3
4
5
6
7
8

Both the recursive and non-recursive solutions produce the same result. However, the non-recursive solution uses a stack to simulate the behavior of recursion, while the recursive solution relies on the call stack.

Detect Palindromes Now let’s explore a more challenging problem: detecting whether a string is a palindrome. A palindrome is a word, phrase, number, or sequence of characters that reads the same forward and backward.

To solve this problem recursively, we can use the following approach:

  1. If the string length is 0 or 1, it is a palindrome.
  2. Otherwise, if the first and last characters are the same, and the substring without the first and last characters is a palindrome, then the string is a palindrome.

Here’s an example implementation:

def is_palindrome(string):
    if len(string) <= 1:  # base case
        return True
    elif string[0] == string[-1] and is_palindrome(string[1:-1]):  # recursive case
        return True
    else:
        return False

Let’s test the function with a few examples:

print(is_palindrome("racecar"))  # True
print(is_palindrome("hello"))  # False
print(is_palindrome(""))  # True

The output will be:

True
False
True

The function correctly detects whether a string is a palindrome or not.

Sort With Quicksort Another common application of recursion is sorting algorithms. Let’s explore how recursion can be used to implement the quicksort algorithm.

Quicksort is a comparison-based sorting algorithm that follows the divide-and-conquer principle. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Choosing the Pivot Item The choice of pivot item can affect the efficiency of the quicksort algorithm. Ideally, the pivot should be the median of the array to be sorted. However, finding the median is a costly operation. In practice, the pivot is usually chosen as the first, last, or middle element of the array.

Here’s an example implementation of a quicksort function:

def quicksort(array):
    if len(array) <= 1:  # base case
        return array
    else:
        pivot = array[0]  # choose the first element as the pivot
        less = [x for x in array[1:] if x <= pivot]  # elements less than or equal to pivot
        greater = [x for x in array[1:] if x > pivot]  # elements greater than pivot
        return quicksort(less) + [pivot] + quicksort(greater)  # concatenate the sorted sub-arrays

Let’s test the function with an example:

array = [5, 2, 8, 6, 1, 9, 3]
sorted_array = quicksort(array)
print(sorted_array)

The output will be:

[1, 2, 3, 5, 6, 8, 9]

The function correctly sorts the array using the quicksort algorithm.

Implementing the Partitioning The quicksort function uses list comprehensions to partition the array into sub-arrays. In each list comprehension, the variable x represents an element from the input array, array.

The less list comprehension selects elements less than or equal to the pivot (x <= pivot). The greater list comprehension selects elements greater than the pivot (x > pivot).

Using the Quicksort Implementation Python provides a built-in sorted function that can be used to sort arrays. However, it’s interesting to compare the performance of the recursive quicksort implementation with the built-in sorted function.

Let’s compare the two implementations using a large array:

import random
import time


array = random.sample(range(1000000), 100000)
start_time = time.time()
sorted_array = quicksort(array)
quicksort_time = time.time() - start_time


start_time = time.time()
sorted_array = sorted(array)
sorted_time = time.time() - start_time


print(f"Quicksort time: {quicksort_time} seconds")
print(f"Sorted time: {sorted_time} seconds")

The output will vary depending on the performance of your computer. However, in general, you will see that the quicksort implementation is slightly slower than the built-in sorted function.

Conclusion In this tutorial, you’ve learned about recursion in Python and how to use it to solve various programming problems. You’ve seen examples of counting down, calculating factorial, traversing a nested list, detecting palindromes, and implementing the quicksort algorithm.

Recursion is a powerful tool for solving problems that can be divided into smaller, identical subproblems. It can lead to elegant and efficient solutions. However, recursion should be used judiciously, as it can consume significant computational resources and may not always be the most efficient approach.

Understanding recursion and its applications can enhance your problem-solving skills and deepen your understanding of algorithms and data structures.

Now it’s time to put your knowledge into practice and explore more problems that can be solved using recursion. Keep learning and exploring Python’s recursive capabilities!