A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

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 get some practice with that first.

We’ll do this by looking at another example: calculating factorials.

A factorial is best illustrated with some examples.

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. ...