Understanding Recursion

By Luke Simpson

February 7, 2024

Introduction

What is recursion? In computer programming, recursion is simply when a function calls itself. While that may sound strange at first, you’ll see how it can actually simplify the solution to certain problems. You can look at it as another tool in your toolbox, and once you know how it works, you may think about the problem you’re facing differently.

In this post, we’ll compare a recursive and iterative approach to two, different problems.

Problem One: Counting to 20

I chose this problem because it will be a simple way to introduce recursion. We’ll use Rust because I like the language and there is a convenient online playground where you can run the following example.

Recursive approach

fn count_to_20(count: u32) {
  if count > 20 {
    return;
  }
  println!("Count: {}", count);
  count_to_20(count + 1);
}

count_to_20(1);

Rust syntax explanation:

fn is a function.
u32 is an unsigned 32-bit integer.
println! outputs to the console.

The first thing to notice is that we have a way to exit the recursive loop. We exit if the count is greater than 20.

If we didn’t have a way to stop recursing, the function would call itself until it caused a stack overflow. Every time a function is called, a new active subroutine is added to the stack. Since the stack can’t store an infinite number of active subroutines, the program crashes.

The exit condition is also called the “base case”. A recursive function has two parts, the base case and the recursive step. Here, the recursive step is where the function calls itself, but increments the count by one. Notice that incrementing the count inches us closer to the base case.

One cool thing about Rust is that if you remove the condition, it will actually warn you.

fn count_to_20(count: u32) {
^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot return without recursing

Understanding how `count_to_20` affects the stack

Whenever a function is called, a “stack frame” gets pushed onto the stack. The stack frame consists of all the parameters and local variables the function needs to run. Here is a rough mental model of how the stack behaves with the count_to_20 recursive function.

We’ll start with an initial count of 19 to save some time.

count_to_20 #1 pushed onto the stack with u32 19.
println pushed onto the stack and prints 19.
println popped off the stack.
count_to_20 #2 pushed onto the stack with u32 20.
println pushed onto the stack and prints 20.
println popped off the stack.
count_to_20 #3 pushed onto the stack with u32 21.
- This is where the exit condition is reached: 21 > 20.
count_to_20 #3 with u32 21 is popped off the stack.
count_to_20 #2 with u32 20 is popped off the stack.
count_to_20 #1 with u32 19 is popped off the stack.

So hopefully this gives you an idea how recursive functions can quickly eat up memory. Until the exit scenario is reached, all data needed by the active subroutines are taking up space.

Iterative approach

Now, obviously for something as simple as outputing numbers from 1 to 20, recursion is not the right tool. It would be much easier to use a loop.

for i in 1..=20 {
  println!("Count: {}", i);
}

So what is a good use-case for recursion?

Problem Two: Traversing a Tree

One good use-case is traversing trees. If you think about an HTML document, it can have many elements, p, div, section, article, etc., and elements can be nested inside each other an arbitrary number of times and can have an arbitrary number of children.

How might recursively traversing an HTML document work? Well, any time an element contains a child element, you just visit that child until you reach an element with no children. That is the base case. At that point, you just return to the previous element to see if it has any more child elements to traverse.

We’ll take a simple example of that and count the number of descendants an element has using recursion. This is the tree we’ll create:

Recursive approach

You can see the finished example of the recursive approach on the Rust Playground.

Here is the structure we’ll be using:

struct Element {
  pub children: Vec<Element>
}

Vec is an array type in Rust. So we have an element whose only purpose is to hold other elements. pub means children is public so we can access it directly.

To make things easy on ourselves, we’ll add a way to create new elements and stub out a count_descendants function.

impl Element {
    pub fn new() -> Element {
        Element {
            children: Vec::new(),
        }
    }

    pub fn count_descendants(&self) -> u32 {
        0
    }
}

impl Element creates a new implementation block where we can add methods for our Element type. Vec::new() creates a Vec of zero length.

Let’s write a test case. We expect root to have 6 descendants, a1 to have three, a2 and b2 to have one, and b1, b3, and c1 to have zero.

#[test]
fn count_descendants_works() {
    let mut root = Element::new();
    let mut a1 = Element::new();
    let mut a2 = Element::new();
    let b1 = Element::new();
    let mut b2 = Element::new();
    let b3 = Element::new();
    let c1 = Element::new();

    assert_eq!(b1.count_descendants(), 0);
    assert_eq!(b3.count_descendants(), 0);
    assert_eq!(c1.count_descendants(), 0);

    b2.children.push(c1);
    assert_eq!(b2.count_descendants(), 1);

    a1.children.push(b1);
    a1.children.push(b2);
    assert_eq!(a1.count_descendants(), 3);

    a2.children.push(b3);
    assert_eq!(a2.count_descendants(), 1);

    root.children.push(a1);
    root.children.push(a2);
    assert_eq!(root.count_descendants(), 6);
}

mut means mutable. Variables are immutable by default in Rust, so we use mut to explicitly show that the variable will change later. assert_eq! asserts that the left side equals the right side or the test fails.

Right now the test fails because count_descendants always returns 0. Let’s complete the method.

pub fn count_descendants(&self) -> u32 {
    let mut num_descendants = self.children.len() as u32;
    for child in &self.children {
        num_descendants += child.count_descendants();
    }
    num_descendants
}

Here, we are not using an explicit condition to stop recursing. Instead, the base case occurs if the number of children is zero. If there are children, the recursive step calls count_descendants for each one. Eventually, a descendant with no children will be found, the method will return 0 without recursing, and the other count_descendants waiting on the stack will be resolved.

If you run the test now, all of our assertions pass.

As you can see, using recursion to count the descendants in the tree makes our job trivially easy. The method itself contains only five lines of code and is easy to reason about.

Iterative approach

Take a moment yourself and see if you can think of an iterative approach to solve the same problem. I think you’ll find it’s not nearly as intuitive as using recursion. This is what I came up with:

pub fn count_descendants(&self) -> u32 {
    let mut count = self.children.len() as u32;
    // Copies self.children to a new Vec that can be changed later.
    let mut elements: Vec<&Element> = self.children.iter().collect();

    while !elements.is_empty() {
        let mut next_elements = Vec::new();
        for element in elements {
            count += element.children.len() as u32;
            // Copies element.children to a new Vec and immediately appends it to next_elements.
            next_elements.append(&mut element.children.iter().collect());
        }
        elements = next_elements;
    }

    count
}

It works by advancing through each level one by one, first the a column, then b, then c. It actually took me a few attempts. At first I was trying to keep track of which index of the arrays and which level I was on manually, but didn’t like where that was going.

To me, iteration is not as elegant to solve this problem. Here are a few reasons why:

We need to track additional state, the elements we’re looping through. With recursion, this isn’t needed. Every element handles its own business.
To me, it’s harder to reason about. If I saw this code in the wild, I think it would take me longer to realize why elements was being replaced with next_elements.
It could be implemented any number of ways, some better than others. Even my first implementation didn’t look as clean. I was using three nested loops. I generally try to limit nesting to two levels and managed to remove one, but the recursive answer seems harder to get wrong.

Conclusion

I hope this helped you wrap your head around recursion, and if you’re not sure whether to use iteration or recursion to solve your next problem, use the one that makes your job easier and is simpler to reason about.

Support the blog! Buy a t-shirt or a mug!

Tags:

Understanding Recursion

Introduction

Problem One: Counting to 20

Recursive approach

Understanding how count_to_20 affects the stack

Iterative approach

Problem Two: Traversing a Tree

Recursive approach

Iterative approach

Conclusion

Understanding how `count_to_20` affects the stack