Easily Understand Recursive Functions in Python

Recursion in Python: An Introduction

What Is Recursion?

Recursion is a coding technique in which a function calls itself. It involves the concept of a recursive definition, where the defined term appears in the definition itself. Recursion allows you to solve certain types of programming problems more effectively.

Why Use Recursion?

While most programming problems can be solved without recursion, there are certain situations where recursion is a powerful tool. Recursive solutions can be more concise and intuitive for problems that have a natural recursive structure. Additionally, recursion can simplify the code and make it easier to understand and maintain.

Recursion in Python

Python fully supports recursion and provides the necessary tools to implement recursive functions. The design of Python functions accommodates recursion by allowing a function to call itself.

Get Started: Count Down to Zero

To understand recursion, let’s start with a simple example of counting down from a given number to zero. We’ll write a recursive function called count_down that takes a positive integer n as input and prints the numbers from n to 0.

def count_down(n):
    if n == 0:
        print(0)
    else:
        print(n)
        count_down(n-1)

In this example, the base case is when n equals 0, and the function simply prints 0. For values of n greater than 0, the function prints n, and then calls itself with n-1 as the argument. This process continues until the base case is reached.

Calculate Factorial

Another common use case for recursion is calculating the factorial of a number. The factorial of a non-negative integer n, denoted as n!, is the product of all positive integers less than or equal to n.

Define a Python Factorial Function

Let’s define a recursive Python function called factorial that calculates the factorial of a given number.

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

In this example, the base case is when n equals 0, and the function returns 1. For values of n greater than 0, the function returns n multiplied by the factorial of n-1, which is obtained by calling the factorial function recursively.

Speed Comparison of Factorial Implementations

To compare the performance of the recursive factorial implementation with a non-recursive one, we can use the timeit module in Python.

import timeit

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

recursive_time = timeit.timeit('factorial(10)', setup='from __main__ import factorial', number=1000)
iterative_time = timeit.timeit('factorial_iterative(10)', setup='from __main__ import factorial_iterative', number=1000)

print(f"Recursive factorial time: {recursive_time}")
print(f"Iterative factorial time: {iterative_time}")

In this example, the timeit module is used to measure the execution time of both the recursive and iterative factorial functions. By running the factorial calculations 1000 times, we can compare the performance of the two implementations. The output will show the execution times for the recursive and iterative solutions.

Traverse a Nested List

Traversing a nested list is another problem that lends itself well to recursion. Let’s explore how to traverse a nested list both recursively and non-recursively.

Traverse a Nested List Recursively

We’ll write a recursive function called traverse_recursive that takes a nested list as input and prints all the elements in a flat format.

def traverse_recursive(lst):
    for item in lst:
        if isinstance(item, list):
            traverse_recursive(item)
        else:
            print(item)

In this example, the function traverse_recursive iterates over each item in the list. If an item is itself a list, the function calls itself recursively with that sublist as the argument. For non-list items, the function simply prints the item.

Traverse a Nested List Non-Recursively

To compare the recursive solution, let’s write a non-recursive function called traverse_iterative that traverses a nested list using a stack.

def traverse_iterative(lst):
    stack = [lst]

    while stack:
        item = stack.pop()

        if isinstance(item, list):
            stack.extend(item[::-1])
        else:
            print(item)

In this example, the function traverse_iterative uses a stack to keep track of the items in the nested list. It starts with the entire list in the stack. While the stack is not empty, the function pops an item from the top of the stack. If the item is a list, the function extends the stack with the reversed sublist. For non-list items, the function prints the item.

Detect Palindromes

Recursion can also be used to determine whether a given string is a palindrome. A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward.

Let’s write a recursive function called is_palindrome that checks whether a given string is a palindrome.

def is_palindrome(string):
    if len(string) <= 1:
        return True
    elif string[0] != string[-1]:
        return False
    else:
        return is_palindrome(string[1:-1])

In this example, the base cases are when the length of the string is 0 or 1, in which case it is considered a palindrome. If the first and last characters of the string are not equal, the function returns False. Otherwise, the function calls itself recursively with the substring excluding the first and last characters.

Sort With Quicksort

Quicksort is a sorting algorithm that can also be implemented using recursion. It works by selecting a pivot element and partitioning the array, such that all elements less than the pivot come before it, and all elements greater than the pivot come after it. This process is then applied recursively to the subarrays.

Choosing the Pivot Item

Let’s start by implementing the quicksort algorithm in Python. To do that, we need to choose a pivot item from the array. A common approach is to select the first item as the pivot.

def quicksort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[0]
    lesser = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]

    return quicksort(lesser) + [pivot] + quicksort(greater)

In this example, the quicksort function handles the base case when the length of the array is 0 or 1, in which case it returns the array as is. Otherwise, it selects the first element as the pivot and creates two subarrays: lesser, which contains the elements less than or equal to the pivot, and greater, which contains the elements greater than the pivot. The function calls itself recursively on lesser and greater, and concatenates the sorted subarrays with the pivot in between.

Implementing the Partitioning

The partitioning process is a crucial step in the quicksort algorithm, as it determines the position of the pivot in the final sorted array. Let’s implement the partitioning step as a separate function called partition.

def partition(arr, low, high):
    i = low - 1
    pivot = arr[high]

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i+1], arr[high] = arr[high], arr[i+1]

    return i + 1

In this example, the partition function takes an array arr, a low index, and a high index as input. It selects the last element as the pivot and initializes an index i to low - 1. It then performs a loop from low to high - 1. If an element is less than or equal to the pivot, i is incremented and the current element is swapped with arr[i]. Finally, the pivot is placed in its correct position by swapping it with arr[i+1], and the function returns the partition index.

Using the Quicksort Implementation

Let’s use the quicksort function to sort an array of integers.

arr = [5, 2, 8, 9, 1, 3]
sorted_arr = quicksort(arr)
print(sorted_arr)

In this example, the arr list contains unsorted integers. By calling the quicksort function on arr, we obtain a new list sorted_arr that contains the same values sorted in ascending order.

Conclusion

Recursion is a powerful technique in Python that allows functions to call themselves, providing elegant and concise solutions to certain types of programming problems. In this tutorial, you’ve learned the basics of recursion in Python and studied various examples, including counting down to zero, calculating factorials, traversing nested lists, detecting palindromes, and sorting with quicksort. By understanding recursion and its applications, you can enhance your problem-solving skills and write more efficient and readable code in Python.