A Simple Python Factorial Program Using Recursion

This article explains a simple and effective way of computing the factorial in a single line of code.

The Basics

Consider the following problem: There are 20 football teams in England’s premier league. Each team can possibly reach any of the 20 ranks at the end of the season. How many possible rankings exist in the premier league, given 20 fixed teams?

Figure: Example of three possible rankings of the football teams in England’s premier league.

The figure shows three different rankings of the teams. In computer science terminology, you would denote each ranking as a “permutation”. A permutation is defined as a specific order of set elements (here: football teams). Using this terminology, our goal is to find the number of permutations of a given set (the set of all football teams). The number of those permutations has important implications in practice such as betting applications, match prediction, and game analysis. For example, when assuming 100 different rankings with equal probability, the probability of a specific ranking is 1/100 = 1%. This can be used as a base probability (a priori probability) for game prediction algorithms. Under these assumptions, a randomly guessed ranking has a 1% probability of being the correct outcome after one season.

How to calculate the number of permutations of a given set? As it turns out, the factorial function n! calculates the number of permutations of a given set of n elements. The factorial is defined as follows:

For example:

Why does the factorial count the number of permutations of a given set of elements? The answer is very straightforward: Say, you have a set of ten elements S = {s0, s1, …, s9} and ten buckets B = {b0, b1, …, b9}. In the football example, there are twenty teams (the elements) and twenty table ranks (the buckets). To get a permutation of S, you could place each element into one bucket using the following algorithm:

  • First, you take a random element from the set S. In how many buckets can you place this element? There are ten empty buckets so you have ten options.
  • Second, you take the next element from the set. In how many buckets can you place this element? There are nine empty buckets so you have nine options.
  • Finally, you take the last element from the set. In how many buckets can you place this element? There is only one empty bucket so you have one option.

In total, you have 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 10! different options. Each option of placing elements into the buckets represents one permutation of the set elements. The number of permutations of a set with n elements is n!.

The Code

You now know everything you need to know to solve the following problem: Write a Python one-liner solution that computes the number of permutations n! of a set with n elements.

## The Data
n = 5

## The One-Liner
factorial = lambda n: n * factorial(n-1) if n > 1 else 1

## The Result

Listing: One-liner solution defining the factorial function recursively.

What’s the output of this code?

How It Works

The factorial function can be defined recursively as

with the recursion base cases defined as

The intuition behind these base cases is the following: A set with one element has one permutation. And a set with zero elements has one permutation (there is one way of assigning zero elements to zero buckets).

The code uses this recursive definition. It creates a lambda function with one argument n. It assigns the lambda function to the name factorial. Finally, it calls the named function factorial(n-1) to calculate the result of the function call factorial(n). By using the solution to the easier problem factorial(n-1), we can construct the solution of the harder problem factorial(n) by multiplying it with the input argument n. As soon as we reach the recursion base case n <= 1, we simply return the hard-coded solution factorial(1) = factorial(0) = 1.

This algorithm shows how one can often find a simple, concise, and efficient way of solving problems by thoroughly understanding the problem first. Choosing the simplest solution idea is one of the most important things you can do when creating your own algorithms. A common problem of beginners is their cluttered and unnecessary complicated code. The recursive definition of the factorial is more readable than an iterative definition (without recursion). As a bonus exercise, try to rewrite this one-liner without using a recursive definition and without external libraries – it’s not trivial and certainly not that concise!

Leave a Comment

Your email address will not be published. Required fields are marked *