A Function That Calls Itself

A Function That Calls Itself

Recursion is a programming technique where a function calls itself within its own body, in order to solve a problem by breaking it down into a smaller version of the same problem.

The idea might seem strange at first: how can a function call itself without running forever? The answer lies in the following principle: at each recursive call, the problem being handled must be smaller (closer to being solved), until it reaches a case simple enough to be solved directly, with no further call.

A classic example: computing the factorial of a number n (written n!), that is, the product of all the integers from 1 to n. By mathematical definition:

# (n! = n times (n-1) times (n-2) ... times 1)
# (in other words: n! = n times (n-1)!)

This definition is already recursive: the factorial of n is defined in terms of the factorial of n minus 1. In Python, this translates directly to:

def factorielle(n):
    return n * factorielle(n - 1)

But watch out: as it stands, this function never stops! It will call factorielle(n-1), which will call factorielle(n-2), and so on, endlessly, until it triggers an error (exceeding the allowed call depth). It is missing one essential ingredient, which you will discover in the next lesson: the base case.