A Common-Sense Guide to Data Structures and Algorithms

Reading Recursive Code

It takes time and practice to get used to recursion, and you will ultimately learn two sets of skills: reading recursive code, and writing recursive code. Reading recursive code is somewhat easier, so let’s first get some practice with that.

Let’s look at another example: calculating factorials.

A factorial is best illustrated with an example:

The factorial of 3 is:

3 * 2 * 1 = 6

The factorial of 5 is:

5 * 4 * 3 * 2 * 1 = 120

And so on and so forth. Here’s a recursive implementation that returns a number’s factorial using Ruby:

def factorial(number)
  if number == 1
    return 1
  else
    return number * factorial(number - 1)
  end
end

This code can look somewhat confusing at first glance, but here’s the ...