# 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