How to Code the Recursive Factorial Algorithm in JavaScript and Python

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 recursive factorial algorithm in JavaScript and Python.

This article originally published at jarednielsen.com

How to Code the Recursive Factorial Algorithm

Programming is problem solving. There are four steps we need to take to solve any programming problem:

1. Understand the problem

2. Make a plan

3. Execute the plan

4. 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 number, `n`
WHEN I run my `factorial` function
THEN my product is calculated recursively

That’s our general outline. We know our input conditions, a whole number greater than zero, and our output requirements, the factorial product of that whole number, and our goal is to calculate the product recursively.

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?

n = 1

The result of n! where n is equal to 1 is 1.

INPUT n

RETURN n

Not much of an algorithm, eh?

The next smallest problem to solve is 2. The result of n! where n is equal to 2 is 2:

2 X 1 = 2

Let's hard code this in pseudocode:

INPUT n

IF n is equal to 1
    RETURN n
ELSE
    RETURN n X 1

This will only return the correct factorial if n is equal to 1 or 2. We'll fix this soon enough.

The next smallest problem is 3. The result of n! where n is equal to 3 is 6:

3 X 2 X 1 = 6

How do we pseudocode this?

We could continue to hard code each increment of n in a conditional statement, but that's not the goal or very pragmatic. It's time to look for a pattern! Let's map out the next few increments of n!:

Do you see a pattern?

Each factorial is composed of the number, n, multiplied by the previous factorial. For example, 5! can also be expressed as:

5 * 4!

And 4! can also be expressed as:

4 * 3!

And so on...

Let's look at it another way. Using 5! as an example, what is 4 in relation to n when n is equal to 5?

n - 1

And what is 3 in relation to n when n is equal to 5?

n - 2

So... another way to write 5!, where n is equal to 5, could be:

n * (n - 1) * (n - 2) * (n - 3) * (n - 4)

Now we can get abstract! In each iteration, n! is equal to n multiplied by n - 1. We can express this in an equation:

n! = n * (n - 1)!

Where have we seen this or something like it before?

Recursion!

What's our base case?

1

What's our recursive case?

n * (n - 1)!

Let's translate this to pseudocode:

FUNCTION factorial
    INPUT n
    IF n IS EQUAL TO 0 OR 1
        RETURN 1
    ELSE
        RETURN n * factorial(n - 1)

Execute the Plan

Now it's simply a matter of translating our pseudocode into the syntax of our programming language.

How to Code the Recursive Factorial Algorithm in JavaScript

Let's start with JavaScript...

const factorial = n => {
    if (n == 0 || n === 1) {
        return 1;
    } else {
        return (n * factorial(n - 1));
    }
 };

How to Code the Recursive Factorial Algorithm in Python

Now let's see it in Python...

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

Evaluate the Plan

Can we do better?

It depends.

While recursion might be mind expanding, it's also space expanding. We want to be concerned about both time and space complexity. Each recursive call to factorial adds another function to the call stack, increasing our memory usage.

A is for Algorithms

Give yourself an A. Grab your copy of A is for Algorithms