Understanding Recursion (Factorial)

Fibonacci sequence is often used to explain recursion (see Understanding Recursion (Fibonacci Sequence)) but recursion may actually be easier to understand.

Recursion

In mathematics, recursion is described as follow:

The factorial of a positive integer \(n\) denoted \(n!\) is the product of all positive integers less than or equal to \(n\).

The sequence can be written like this:

$$ n! = \begin{cases} 1 & \quad \text{, } n = 0 \\ n * (n - 1)! & \quad \text{, } n > 0 \end{cases} $$

The beginning of the sequence is thus:

1, 1, 2, 6, 24, 120, 720, 5 040, 40 320, 362 880, 3 628 800, 39 916 800…

How it Translates in Programming

Using a recursion, we can easily write a factorial:

def factorial(n)
  return 1 if n == 1
  n * factorial(n - 1)
end

The recursion is on line three.

Trying to translate the behavior of factorial(3) (\(3!\)) step by step:

Call factorial(3):
  Line 3: 3 * factorial(2)

  Call factorial(2):
    Line 3: 2 * factorial(1)

    Call factorial(1):
      Line 2: this time n == 1
      factorial(1) returns 1

    Back in factorial(2) call
    Line 3: 2 * factorial(1) = 2 * 1
    Return 2

  Back in factorial(2) call
  Line 3: 3 * factorial(2) = 3 * 2
  Return 6

Back in factorial(3) call which returns 6

This behavior is the same as calling multiple method and using its return value:

def factorial1
  1
end

def factorial2
  2 * factorial1
end

def factorial3
  3 * factorial2
end