Understanding Recursion in Python

What’s Inside?

Recursion is a concept that I initially found challenging to grasp. It didn’t come naturally to me, and I still sometimes have to look it up when I need to use it. I decided to write this article to demystify recursion and node down some Python code snippets that might come in handy.

This article talks about the basics of recursion aimed at building intuition around what is recursion and when to use it. The next article has three examples of how recursion is used real world. You can skip to this and go to that directly if you’re already familiar with the basics.

What is recursion exactly?

Recursion occurs when a function calls itself as part of its execution.

This statement might not add up immediately. But let’s look at the example, see the diagram, run the code below and you will get it.

Factorial is the best example to build intuition for recursion. Let’s see the process of calculating 7!

7! = 7 x 6!

To find 7! you need to find 6! and so on, until you reach the base case of 1! The diagram below illustrates this process.

The factorial function works by multiplying the current number by the factorial of (number — 1).

Recursive functions stop when they reach the base case. At this point, the function returns a value instead of calling itself again. This value is then used in the previous step, and the process continues backwards until the first call is completed.

Factorial Code And Output

This code calculates the factorial of a given number using recursion. Run it in Google Colab and try experimenting with different inputs. This code has print statements to make execution intutive.

def factorial(n, depth=0):
    
   # This code block if to create visualy intutive output
   # It's safe to ignore depth part and focus on recursion
   # Create an indentation based on the recursion dept
    indent = "  " * depth  
    print(f"{indent}factorial({n}) called.")

    # Actual code starts here
    # Base case: if n is 0 or 1, return 1
    if n == 0 or n == 1:
        print(f"{indent}Returning 1 (base case)")
        return 1

    # Recursive case: n * factorial of (n-1)
    result = n * factorial(n - 1, depth + 1)
    print(f"{indent}Returning {n} * factorial({n - 1}) = {result}")
    return result

# Example usage:
number = 7
print(f"Calculating the factorial of {number}:\n")
result = factorial(number)
print(f"\nThe factorial of {number} is {result}")

Output

Notice how the factorial function, when called with 7, goes inside and calls the factorial for 6, then for 5, and so on until it hits the base case.

The base case, which is 1 in this scenario, does not call the factorial function again. Instead, it returns the output (1 in this case), which is then used as input for the previous steps to calculate their respective outputs.

Calculating the factorial of 7:

factorial(7) called.
  factorial(6) called.
    factorial(5) called.
      factorial(4) called.
        factorial(3) called.
          factorial(2) called.
            factorial(1) called.
            Returning 1 (base case)
          Returning 2 * factorial(1) = 2
        Returning 3 * factorial(2) = 6
      Returning 4 * factorial(3) = 24
    Returning 5 * factorial(4) = 120
  Returning 6 * factorial(5) = 720
Returning 7 * factorial(6) = 5040

The factorial of 7 is 5040

If you are new to recursion, stop here and revisit the diagrams above. Read the definition recursively until you reach a solid understanding.

When To Use Recursion

Recursion is particularly powerful for problems that can be broken down into smaller, self-similar tasks or involve hierarchical data. Here are some key indicators to look for:

Self-Similar Sub-Problems:

If a problem can be broken down into smaller, similar versions of itself, recursion might be a natural fit. For instance, calculating factorials or generating Fibonacci numbers are classic examples where the problem can be expressed in terms of smaller instances of the same problem.

Hierarchical Structures:

Problems involving trees, graphs, or nested elements often benefit from a recursive approach due to their layered nature. For example, traversing a tree or parsing nested data structures like HTML or JSON are tasks where each element can be processed in the same way as its sub-elements.

Backtracking Solutions:

When a problem involves exploring multiple paths or combinations and reverting to previous states (like puzzles or constraint satisfaction problems), recursion simplifies the implementation. Problems like the N-Queens puzzle or maze solving use recursion to explore possibilities and backtrack when a path fails.

Mathematical Recurrence:

Problems defined by recurrence relations (like Fibonacci or factorial) are inherently recursive. These problems are naturally suited for recursion as their definitions involve calling the same function with smaller arguments, making the recursive approach both intuitive and efficient.

By understanding these indicators, you can recognize when recursion is the most elegant and effective solution. Next, let’s look at some real-life examples solved using recursion.

Conclusion

Recursion allows you to break down complex tasks into simpler, self-referential steps, making it easier to manage and solve problems that involve hierarchical data, repetitive structures, or nested tasks. By mastering recursion, you can enhance your ability to think algorithmically and develop more elegant solutions to a wide range of challenges.

In the next article, we’ll explore real-world examples of recursion applied to practical problems like file system navigation, warehouse management, and financial data processing.