Factorial and the Sum of the First n Integers

Factorial and the Sum of the First n Integers

You have already seen the factorial; here is a second classic example of recursion: the sum of the first n integers, that is, 1 + 2 + 3 + ... + n.

This sum is defined recursively as follows: the sum up to n equals n plus the sum up to n minus 1. The base case is n equals 0: the sum up to 0 is 0.

def somme(n):
    if n <= 0:
        return 0                # (base case)
    else:
        return n + somme(n - 1) # (recursive case)

print(somme(5))   # (prints 15, since 1+2+3+4+5 = 15)

Compare this recursive version to a classic version using a loop:

def somme_iterative(n):
    total = 0
    for i in range(1, n + 1):
        total = total + i
    return total

Both functions return exactly the same result. Recursion is therefore not the only solution: it is often a matter of clarity. For a problem that is naturally defined in terms of a smaller version of itself, the recursive version is sometimes more readable and closer to the problem's mathematical definition.

Let's revisit the factorial with another trace example, factorielle(4):

# factorielle(4) = 4 * factorielle(3)
# factorielle(3) = 3 * factorielle(2)
# factorielle(2) = 2 * factorielle(1)
# factorielle(1) = 1   (base case reached)
# so factorielle(4) = 4 * 3 * 2 * 1 = 24

Remember the general method for building a recursive function: first identify the simplest base case, then express the general case in terms of a smaller problem that moves closer to that base case.