Computer Science : Recursion in Python

Introduction

Recursion is a way of solving a problem by having a function calls itself.

In this article we will use factorials as an example with Python.

Do you remember what are factorials ? Pretty easy :

n! = n * (n-1) * (n-2) * (n-3) * (n-4) * …. * 3 * 2 * 1

So for example :

and just FYI : 0! = 1

In this example we will develop a function to calculate factorials like fact(parameter) using recursion.

In our function explained below, we can find a pattern :

n! = n * (n-1) * (n-2) * (n-3) * (n-4) * …. * 3 * 2 * 1

As, you can see, this part is also a factorial ! (n-1)!

So we can rewrite n! is in a way

n! = n * (n-1)!

But let’s be careful, it doesn’t work if n=0, so we will have to handle that exception (if n is equal or superior to 1).

Now we have to use recursion to develop our function.

In this script, you can see that we are using recursion because the function calls itself :

Thanks for your attention !