The Base Case: The Key to Correct Recursion

The Base Case: The Key to Correct Recursion

Every correct recursive function needs a base case: a simple condition, with no recursive call, that stops the chain of calls and directly returns a result.

For the factorial, the natural base case is 0! equals 1 (by mathematical convention), or 1! equals 1. Here is the complete, correct version:

def factorielle(n):
    if n <= 1:
        return 1                      # (base case: stops the recursion)
    else:
        return n * factorielle(n - 1) # (recursive case)

Let's trace through factorielle(3):

• factorielle(3) calls 3 * factorielle(2)
• factorielle(2) calls 2 * factorielle(1)
• factorielle(1) reaches the base case: returns 1, with no further call
• factorielle(2) can then compute 2 * 1 = 2
• factorielle(3) can then compute 3 * 2 = 6

The final result is indeed 6, which matches 3 times 2 times 1.

Rule to remember: every recursive function must contain at least two elements:

1. a base case (or several), which returns a value directly, with no recursive call,
2. a recursive case, which calls the function on a strictly smaller problem, moving closer to the base case.

If you forget the base case, or if the recursive case never moves closer to the base case (for example, by mistakenly calling factorielle(n + 1)), the function calls itself indefinitely: this is infinite recursion, which eventually triggers an error (RecursionError in Python).