Understanding Recursion Through Practical Examples

Just like many great ideas in history, recursion was discovered by accident. A mathematician named Edouard Lucas stumbled upon the concept in 1883 while trying to solve a problem concerning Fibonacci numbers. Recursion is now a fundamental technique employed by software engineers for solving complex problems.

Recursion is a fascinating topic and can produce elegant code solutions. It also has an intimidating reputation: it often creates confusion and is considered a necessary hurdle to overcome to understand many popular algorithms. Don’t worry! Recursion isn’t as hard to understand as it is to teach.

This blog post will serve as an introduction to recursion fundamentals, provide practical examples of how it can be used in real-world scenarios, and you’ll learn how to write a simple recursive function in Python that you can build upon in your projects. Stay tuned for future posts that will explore specific applications of recursion in more detail. By the end of this article, you’ll see that recursion is a powerful tool that should be part of every software engineer’s toolkit. So without further ado, let’s get started!

Recursion is a subset of mathematics and computer science that deals with the idea of self-reference. It’s a technique that allows your computer to break down a task into smaller and smaller pieces until it’s easy to solve.

A function may call other functions, including calling itself. A function that calls itself is known as a recursive function, and the technique of employing a recursive function is called recursion.

The word ‘recursion’ comes from the Latin word recurrere, meaning to run or hasten back, return, revert, or recur.

Recursion in the Real World

To help you understand how recursive algorithms work, let’s take a look at a few examples of recursion in the real world.

People often sort stacks of documents using a recursive method. For example, imagine you are sorting 100 documents with names on them. First, you place documents into piles by the first letter, then sort each pile.

Feedback loops in a hierarchical organization is another example of recursion. The top boss tells top executives to collect feedback from everyone in the company. Each executive gathers his/her direct reports and tells them to gather feedback from their direct reports. And on down the line. People with no direct reports — the leaf nodes in the tree — give their feedback. The feedback travels back up the tree with each manager adding his/her own feedback. Eventually, all the feedback makes it back up to the top boss.

Yet another real-world problem solved by recursion would be nesting dolls. You create a function called open_doll(). Given a stack of them, you would recursively open the dolls, calling open_doll(), until you’ve reached the innermost doll.

Examples of Recursion in Software Engineering

Recursive algorithms can be used for sorting and searching data structures such as linked lists, binary trees, and graphs. They are also often used for string manipulation tasks such as checking if two strings are anagrams or finding the longest common subsequence between two strings. Another common use case for recursion is traversing complex data structures such as JSON objects or directory trees on file systems. Finally, they can also be used to generate fractals or create animation effects using recursive rendering techniques.

Do I Need to Use Recursion?

Most programming problems are solvable without recursion. So, strictly speaking, recursion usually isn’t necessary. However, recursion provides a powerful alternative for performing repetitions of tasks in which a loop is not ideal. It’s useful for finding all possible subsets of a set of items, such as all possible reordering of a word’s letters, all possible subsets of items, all possible paths between cities, etc.

On the other hand, recursion isn’t for every situation. Here are some other factors to consider:

• For some problems, a recursive solution, though possible, will be confusing rather than elegant.
• Recursive implementations often consume more memory than non-recursive ones.
• In some cases, using recursion may result in a slower execution time.

Typically, the readability of the code will be the biggest determining factor. But it depends on the circumstances. The examples presented below should help you get a feel for when you should choose recursion.

When you call a function in Python, the interpreter creates a new local namespace so that names defined within that function don’t collide with identical names defined elsewhere. One function can call another, and even if they both define objects with the same name, it all works out fine because those objects exist in separate namespaces. The same is true if multiple instances of the same function are running concurrently.

Example 1:

def count_down(count):
#we need a way to end our countdown at 0 and prevent 
#the recursion from continuing on forever
    if count == 0:            
        print('Go!')                  
    else:                        
        print(count)             
        count_down(count-1)        
            
count_down(2)

1. count_down is called and count = 2.

2. count_down is recursively called and count = 1.

3. count_down is recursively called and count = 0.

Base Case and Recursive Case

Recursion has two fundamental aspects: the base case and the recursive step.

Creating a recursive function can be accomplished in two steps:

1. Write base case — Every recursive function must have a case that returns a value without performing a recursive call. That case is called the base case. You may write that part of the function first and then test it. There are one or more base cases that are directly solvable without the need for further recursion. Without a base case, it’s the iterative equivalent of writing an infinite loop.

2. Write recursive case — Then add the recursive case to the function. Each recursive call moves the solution progressively closer to a base case.

In a recursive function, the “counting variable” equivalent is the argument to the recursive call. If we’re counting down to 0, for example, our base case would be the function call that receives 0 as an argument. We might design a recursive step that takes the argument passed in, decrements it by one, and calls the function again with the decremented argument. In this way, we would be moving towards 0 as our base case.

Example 2:

names = [ "Li", [ "Tammy", [ "Will", "Bob" ], "Tomoko", "Jim" ],
         "Alex", [ "Colin", "Chad"], "Ann" ]

Suppose you wanted to count the number of leaf elements in this list — the lowest-level str objects — as though you’d flattened out the list. The leaf elements are “Li”, “Tammy”, “Will”, “Bob”, “Tomoko”, “Jim”, “Alex”, “Colin”, “Chad”, and “Ann”, so the answer should be 10.

Just calling len() on the list doesn’t give the correct answer. len() counts the objects at the top level of names, which are the three leaf elements “Li”, “Alex”, and “Ann” and two sublists [“Tammy”, [“Will”, “Bob”], “Tomoko”, “Jim”] and [“Colin”, “Chad”]:

for index, item in enumerate(names):
    print(index, item)

Output:

0 Li
1 ['Tammy', ['Will', 'Bob'], 'Tomoko', 'Jim']
2 Alex
3 ['Colin', 'Chad']
4 Ann

What you need here is a function that traverses the entire list structure, sublists included. The algorithm goes something like this:

1. Walk through the list, examining each item in turn.

2. If you find a leaf element, then add it to the accumulated count.

3. If you encounter a sublist, then do the following:

• Drop down into that sublist and similarly walk through it.
• Once you’ve exhausted the sublist, go back up, add the elements from the sublist to the accumulated count, and resume the walk through the parent list where you left off.

Traverse a Nested List Recursively

Recursion fits this problem very nicely. To solve it, you need to be able to determine whether a given list item is a leaf item or not. For that, you can use the built-in Python function isinstance().

In the case of the names list, if an item is an instance of type list, then it’s a sublist. Otherwise, it’s a leaf item:

names = [ "Li", [ "Tammy", [ "Will", "Bob" ], "Tomoko", "Jim" ],
         "Alex", [ "Colin", "Chad"], "Ann" ]

print(isinstance(names[0], list)) #False
print(isinstance(names[1], list)) #True
print(isinstance(names[1][0], list)) #False
print(isinstance(names[1][1], list)) #True

We can solve the problem using an algorithm like this:

def count_leaf_items(item_list):
    count = 0
    for item in item_list:
        if isinstance(item, list):
            count += count_leaf_items(item)
        else:
            count += 1
    return count

count_leaf_items(names) # output is 10

For more visual examples of a recursive function, check out Recursion Visualizer created by Pamela Fox. This site offers an interactive way to visualize the call graph of recursive functions. Another helpful recursion visualization can be found here. Professor David Galles developed interactive animations for a variety of data structures and algorithms, including recursion. Start with Reversing a String.

Key Takeaways:

• Recursion is a concept in computer programming where you can break down a complex problem into smaller, simpler versions of itself until you arrive at a solution. This technique is often used when dealing with data structures and algorithms.
• Three rules of recursion are: (1) a recursive algorithm must have a base case, (2) it must change its state and move toward the base case, and (3) it must call itself recursively.
• Any algorithm you can write recursively, you can also write iteratively. The main advantage of recursion is how elegant it is — it takes fewer lines of code.
• The disadvantage of recursive algorithms is that they often take up more memory because they have to hold data on Python’s internal stack. They can also be more difficult than iterative algorithms to read and debug because it’s harder to follow what’s happening in a recursive algorithm.
• Be careful with recursion as it can be quite easy to slip into writing a function that never terminates, or one that uses excess amounts of memory. However, when written correctly recursion can be a very efficient and mathematically-elegant approach to programming.

In summary, recursion is an incredibly powerful tool that software engineers can use to simplify complex problems by breaking them down into smaller sub-problems without any additional recursions or looping constructs. While this technique does come with certain disadvantages such as increased memory usage due to its reliance on stack frames, its advantages far outweigh these drawbacks when used judiciously in software engineering projects. Stay tuned for future posts that will explore specific applications of recursion in more detail.