The Self-Taught Computer Scientist

Introduction to Algorithms
20
the_product = 1
while n > 0:
the_product *= n
n = n - 1
return the_product
Your function, 
factorial
, accepts the number, 
n
, that you are using in your calculation.
def factorial(n):
Inside your function, you define a variable, 
the_product
, and set it to 1. You use 
the_product
to 
keep track of the product as you multiply 
n
by the numbers preceding it, for example, 5 * 4 * 3 * 2 * 1.
Next, you use a 
while
loop to iterate backward from 
n
to 1 while keeping track of the product.
while n > 0:
the_product *= n
n = n - 1
At the end of your 
while
loop, you return 
the_product
, which contains the factorial of 
n
.
return the_product
Here is how to write the same algorithm recursively:
def factorial(n):
if n == 0: 
return 1
return n * factorial(n - 1)
First, you define a function called 
factorial
that accepts the number, 
n
, as a parameter. Next comes 
your base case. Your function will call itself repeatedly until 
n
is 0, at which point it will return 
1
and 
will stop calling itself.
if n == 0:
return 1
Whenever the base case is not satisfied, this line of code executes:
return n * factorial(n - 1)
As you can see, your code calls the 
factorial
function, which is itself. If this is your first time 
seeing a recursive algorithm, this probably looks strange to you, and it might even look like this code 
could not possibly work. But I promise you it does work. In this case, your 
factorial
function calls 
itself and returns the result. However, it does not call itself with the value of 
n
; rather, it calls it with 
the value of 
n
− 1. Eventually, 
n
will be less than 1, which will satisfy your base case:

---