Algorithms 101: Princesses, Peas and Recursion in Ruby

Noob v. Algorithms, #11, how I learned to stop hating recursion

Do you FEAR recursion? Well, fellow Noobs, I did too, as recently as a few days ago. I had read many excellent blog posts about recursion, and I felt like I understood a bit of it. But just hearing the word made me slightly ill.

My aha moment came from … Grokking Algorithms by Aditya Bhargava. If this isn’t a best seller, I’m not sure why not! (No, I don’t get any money for promoting this book). But if you want a great explanation with big, beautiful drawings, this book is for you. Here is a free preview . (I ended up buying a used(?) version of the e-book on eBay for $5).

Short and sweet intro: A recursive function is one that calls itself. Now for the explanation …

The Princess and the Pea

Do you remember this Hans Christian Anderson fairy tale? In it, a prince wants to marry a princess, but he wants to marry a real princess.

How will he know if she’s real? Well, a real princess is super delicate(humor me, I didn’t write the tale, Hans did). She is sooooo delicate that if she slept on a pile of mattresses, and if there were a pea anywhere in that pile, our delicate princess would not be able to sleep because the pea would offend her delicate self. Mere mortals, of course, would never notice.

To learn recursion, let’s imagine that you are sleeping on top of a stack of mattresses, and you notice something trying to poke through. Probably a pea! You can’t sleep, so you try to find it. You are determined. You are going to look under one mattress at a time until you can find and remove find the offending legume!

Steps for finding the pea

Let’s say you want to write instructions for how to find the pea. You could say:

1. look under the top mattress.
2. If you find the pea, your work is done!
3. If you another mattress, look under it.
4. If you find the pea, your work is done!
5. If you find another mattress, look under it
6. If you find the pea, your work is done!
7. If you find another mattress….

Obviously, there’s a pattern here. Those 7 steps above are really just 3 simple steps, repeated:

1. Look under mattress
2. If you find a pea, your work is done! Forget about step 3. Woot!
3. If you find another mattress, start again from step 1.

Stack of mattresses

So here’s what a stack of mattresses would look like in code:

Suspension of disbelief

For the sake of learning the concept of recursion, forget what you know about arrays for a moment and try to imagine the items above as being in a physical stack. The first item in the array is at the bottom of the stack. We want to look at one mattress at a time, starting with the top of the stack.

Now let’s code.

Remember, we’re going to look at one item at a time, starting with the top of the stack. So let’s use ‘pop’ to pop off the top (last) item in the array. We’ll call it current_item, because it’s the current item we’re looking at.

def find_pea(stack)

let current_item = stack.pop

#more code here
   
end

When we look our current item, we’re going to do one of two things. If it’s the pea, our work is done! But if it’s another mattress, we’ll have to start all over again.

  if current_item === "pea"
    return "found! Now I can get a good night's sleep"
  else
    puts "No pea here!"
    find_pea(stack)
  end

There are two things going on here (not in this order …)

1. If we don’t find the pea, the function calls itself again, passing in stack as an argument.
2. We establish a way to exit the function instead of calling it again. that’s called a “base case”. Our base case is finding the pea. Once found, our work is done. We return a value (a string in this case). In Ruby, the return makes us exit the loop. Since there is no more logic after the loop, we also exit the entire function.

Warning: Without a base case, a recursive method will call itself again and again and again … in other words, it will be an infinite loop.

So far, we have this:

def find_pea(stack)

current_item = stack.pop()

if current_item === "pea"
    #base case:
    return "found! Now I can get a good night's sleep!"
  else
    puts "This is not a pea! This #{current_item}"
    find_pea(stack)
  end
end

find_pea(stack)

Wait, what if there’s NO pea?

We included a pea in our test array, but what if we want to test our method against different piles of mattresses that may or may not include a pea? If there’s no pea under the last mattress of any given stack of mattresses, our function should stop.

But the way we wrote it, it keeps going. After we’re done with the last mattress, it will pass an empty array stack = [] back into the argument. When we run this line

current_item = stack.pop()

current_item will equal nil. Then we’ll check to see if nil is equal to “pea” and of course it won’t be, so we end up calling find_pea(stack) again. In other words, we created an … infinite loop! AAAGH!

We need another base case

Recursive methods have at least one base case. Our first base case exits the function when we find the pea. Our second base case should exit the function if we finish looking through all of the mattresses without finding the pea.

Each time we start the loop, let’s see if our stack is empty. If it is, let’s exit by returning a value.

  if stack.length > 0
    current_item = stack.pop()
  else
    return "drat! couldn't find it!"
  end

All together now:

You can step through the code here, on PythonTutor.com(which uses many languages, including Ruby, despite the name!)

You can also play with it here, on repl.it.

Back to real life

In real life, you do not use recursion to search for a particular string in an array of five strings (there are way easier ways to do that, which I won’t cover here!).

So when do you use recursion? You use it when you need to run the same operation on progressively smaller or more deeply nested parts of a problem.

The classic use case for recursion is to traverse a file tree, which you could do like so:

pseudocode for printing names of all pdfs in file tree

def recursively_search_file_tree(directory)
   if directory is empty 
      return "all done!"
   else 
      directory.each do |item|
        if item is a file with extension .pdf 
           puts item name
        elsif item is a folder
           recursively_search_file_tree(folder)
        end
     end
   end
end

Here’s hoping you like recursion a little more than you did at the start of this post!

Copyright © Joan Indiana Lyness 2019

in case you missed it: Algorithms 101, #10, Birthday Chocolate in JavaScript