If you want to learn how to code, you need to learn algorithms. Learning algorithms improves your problem solving skills by revealing design patterns in programming. In this tutorial, you will learn how to code the factorial algorithm in JavaScript and Python.
Give yourself an A. Grab your copy of A is for Algorithms
Retrieval Practice
Retrieval practice is the surest way to solidify any new learning. Attempt to answer the following questions before proceeding:
-
What is a factorial?
-
How does iteration work?
-
What is multiplication assignment?
What Is A Factorial?
A factorial is the product of all positive integers less than or equal to n.
We write that as n!.
For example, 5!:
5 * 4 * 3 * 2 * 1 = 120
How Does Iteration Work?
According to Ye Olde Wikipedia:
Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration.
We use for
and while
loops to iterate.
What is Multiplication Assignment?
We can reassign the value of a variable to the product of that variable multiplied by another value using the multiplication assignment.
Both Python and JavaScript feature the *=
operator.
The following expression:
x = 2
x *= 2
Is equivalent to:
x = 2
x = x * 2
Let’s Get Meta
Ask yourself the following questions and keep them back of mind as you proceed:
-
Why do I need to know this?
-
How can I increment a variable with multiplication?
-
How does a for loop work?
How to Code the Factorial Algorithm
Programming is problem solving. There are four steps we need to take to solve any programming problem:
-
Understand the problem
-
Make a plan
-
Execute the plan
-
Evaluate the plan
Understand the Problem
To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:
GIVEN a whole number, n
WHEN I pass it to an iterative factorial function
THEN I am returned the factorial of n
That’s our general outline. We know our input conditions, a whole number, and our output requirements, the factorial of that number, and our goal is to calculate the factorial iteratively.
Let’s make a plan!
Make a Plan
Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:
-
Decomposition
-
Pattern recognition
-
Abstraction
-
Algorithm design
The first step is decomposition, or breaking our problem down into smaller problems. What’s the smallest problem we can solve?
0!
What’s the factorial of 0?
1
What?
A factorial is the number of permutations of another number. There’s only one way to arrange 0, so 0! is 1.
If n
is equal to 0, we know our factorial
function needs to return 1.
Let’s start pseudocoding this:
INPUT n
SET result to 1
IF n == 0
RETURN result
What’s the next smallest problem we can solve?
1!
What’s the factorial of 1?
Also 1.
Same as 0 above, there’s only one way to arrange 1.
I promise it’s going to get more fun with 2, but first, let’s add this to our pseudocode:
INPUT n
SET result to 1
IF n == 0 OR n == 1
RETURN result
Sweet. Now, what’s the factorial of 2?
It’s 2!
Isn’t that fun?
But why is 2! equal to 2?
We can express 2! as 2 * 1.
We don’t want to hard code this, so now we need to start looking for a pattern.
Table time!
n | n! | 1 * … n |
---|---|---|
2 | 2 | 1 * 2 |
3 | 6 | 1 * 2 * 3 |
4 | 24 | 1 * 2 * 3 * 4 |
5 | 120 | 1 * 2 * 3 * 4 * 5 |
In the table above, we can see our input, n
, the product of n!
, and the “long hand” expression of the multiplication of the sequence.
Where have we seen this or something like it before?
Iteration!
As n
increases, so does the number of multiplications required to calcuate the product of n!
.
Because we already addressed 0 and 1, we can start our loop at 2.
But what do we do in the loop?
We need to reassign the value of result
to the product of result
multiplied by i
.
Our final pseudocode looks like this:
INPUT n
SET result TO 1
IF n == 0 OR n == 1
RETURN result
FOR EVERY VALUE i BETWEEN 2 AND n
SET result TO THE PRODUCT OF result MULTIPLIED BY i
RETURN result
Execute the Plan
Now it’s simply a matter of translating our pseudocode into the syntax of our programming language.
How to Code the Factorial Algorithm in JavaScript
Let’s start with JavaScript…
const factorial = n => {
let result = 1;
if (n == 0 || n == 1) {
return result;
}
for (let i = 2; i <= n; i++) {
result = result * i;
}
return result;
}
How to Code the Factorial Algorithm in Python
Now let’s see it in Python…
def factorial(n):
result = 1
if n == 0 or n == 1:
return result
for i in range(2, n + 1):
result = result * i
return result
Evaluate the Plan
Can we do better?
This approach does not address negative numbers. In both Python and JavaScript, if we call factorial
with a value of -5, it will return 1. This is happening because none of our conditions are being met, in both the if
block and the for
loop.
Both Python and JavaScript feature factorial methods in their math modules.
What is the Big O Of Factorial?
If you want to learn how to calculate time and space complexity, pick up your copy of The Little Book of Big O
Reflection
Remember those meta questions we asked at the outset? Let’s make it stick and answer them now!
-
Why do I need to know this?
-
How can I increment a variable with multiplication?
-
How does iteration work?
Why Do I Need to Know This?
While you will probably never code the factorial algorithm professionally, you might code a factorial algorithm accidentally, which is something to be avoided. Understanding the concept of factorial is important when calculating the space and time complexity of algorithms. It’s also important when calculating permutations and combinations. Stay tuned!
How Can I Increment a Variable With Multiplication?
We can increment a variable with multiplication by using the multiplication operator and/or variable reassignment and reassigning the value of our variable to the product of that variable multiplied by an iterator.
How Does A For Loop Work?
A for
loop is a control flow statement used for iteration. We declare a for
loop with
When using a for
loop, we specify an iterator, often i
, and a condition, such as i < arr.length
, followed by an operator to advance the iteration, often i++
. We generally initialize a for
loop with i = 0
, but, as we saw above, we can start counting with any value. Furthermore, we can increment (or decrement, for that matter) by any value, not just 1. We would simply use the += x
operator, where x
is the value by which we want to increment our loop. In our loop is a statement that is executed with each iteration.
Initialization
Condition
Statement
A is for Algorithms
Give yourself an A. Grab your copy of A is for Algorithms