Factoral and Recursion

We all remember factorals from school but to remind us what they are, a factoral is the product of all the positive integers less than or equal to the initial number(n):

n!= n \times n-1 \times \ldots \times 2 \times 1

For example:

6!=6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720

Strangely 0!=1 there is a mathematical proof which states why but I will not be expanding on it here, I will however be taking advantage of this for the function.

Simple Solution

A simple function for working this out would be to simply loop round until the desired number is reached, and multiplying the result by the next value in the loop. Since we already know that 0!=1 we can initialise result to 1. The function would be simply:

def factoral(n):
	result = 1
	for i in range(1, n+1):
		result = result * i
	return result

Running this function with a value of 6:

>>> factoral(6)
720

Which is exactly the result we wanted, the program works, but there is a better way, a way which uses a programming super power, the power of recursion.

Recursion

Before we write the recursive version of the function, we first need to be introduced. Recursion is when a program or function calls or relies on itself to break the problem into smaller parts. There are two main rules in recursion, these are that they:

1. must have a base case.
2. must call themselves.

So what is a base case, this is a known value which is used as a termination condition. Looking back at the factoral problem we already know the base case is 0!=1. Now we just need to call factoral to give a picture of this we know that:

3!=3 \times 2 \times 1 = 6

Which can be seen as:

fact(3) = fact(3) \times fact(2) \times fact(1) \times fact(0)

Which can be simplified as:

fact(n) = n \times fact(n-1)

This gives us out to conditions for the function which is defined as follows:

fact(n) = \begin{cases}
1 & \textit{if } n=0\\
n \times fact(n-1) & \textit{if } n>0
\end{cases}

We can now rewrite the factoral function as:

def factoral(n):
	if n == 0:
		return 1
	else:
		return n * factoral(n-1)

Running this function with a value of 6 gives:

>>> factoral(6)
720

This is exactly what we wanted to achieve, but how does it work. The program uses something called the call stack, each time the recursion happens the value of n is put onto the stack and once all the values have been calculated the function rewinds.

The Image on the left shows the item n=6 being popped off the stack. When using recursion the resulting calculation will be performed as each item is popped and the result returned.