Recursion in Ruby

What does recursion mean?

Merriam Webster provides the following definition:

"a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls itself one or more times until a specified condition is met at which time the rest of each repetition is processed from the last one called to the first"

Recursively solving a problem means that you create a method that calls itself until it reaches a base problem and then exits. There are two important things to be aware of when deciding if a problem can be solved recursively. The first thing is that there must be a way out of the recursive loop, or it will loop indefinitely. The second thing to look for is a problem that has a basic solution and another equally difficult solution that can eventually solve the basic solution.

What does recursion look like in Ruby?

Recursion is typically shown with mathematical problems that express the equivalence of the basic solution to the recursive solution but don't appear to be practical outside of those uses. This article will look at solving two problems, factorial and another example that isn't solving a math problem.

Factorial

def fact n   
  return 1 if n < 2
  n * fact(n - 1)
end

Why does this work?

Ruby makes understanding the two key concepts for recursion easy with each of these lines.

return 1 if n < 2

This is our escape from the recursion. You will see from the second line that n decrements each time through the recursion, so we will eventually escape the loop as long as we start with a positive number. (No, I'm not going to handle errors, this is about recursion)

n * fact(n - 1)

This is where the recursion actually begins. What happens on this line is Ruby stays here and continues to call #fact until it hits the escape point. To understand this better, comment out the first line and then call puts fact(10) to see what happens.

It's not terribly important to understand all of the inner workings of how this happens for you, just know that Ruby will unwrap the entire recursive loop until the basic problem and then return the entire result. The final line returns our result so this is where Ruby starts the recursion and returns its result. It knows to return a result because it will eventually call 1 * fact(2 - 1) and get 1 as a return and there will be no more loops to go. The next step for Ruby is to return the result of the recursive loop.

Math hurts, do something else.

Recursion is not limited to math problems, let's build a recursive CLI menu and see a more practical use.

def menu selection=nil
  system 'clear' #clears the screen
  puts 'Menu'
  puts '-----'
  puts '1. Email'
  puts '2. Chat'
  puts '3. Account'
  puts '4. Quit'
  puts "You chose #{selection}" unless selection.nil? 
  selection = gets.chomp
  return 'You selected quit' if selection == '4' # this is the escape. Note '4' is a string.
  menu selection # this is the recursion
end

Although the menu doesn't actually do anything useful, it illustrates how a method can call itself and pass new information to itself each time. Let's say you were making a call to an API that provided a random trivia fact, only you wanted a new random fact each time and the API would sometimes send you a fact you had seen before. Recursion would be a simple solution since you only need to check if the fact you received is in your list of known facts and if it is, call the method to retrieve the fact again. If it isn't, then present the fact. It would be prudent to provide an additional break so that you will stop if the API only sends you facts you have already seen.

Hopefully this sheds some light on recursion and how it can be practically applied in your use case. If your problem is a "Do this until..." and there is an escape condition that will occur either through user input or by your method passing a new variable to itself that will eventually match the escape condition, then recursion may be right for you.

Please share if this was helpful and thanks for reading.