Understanding recursion

Recursion is a process of internal, nested repetition. A well-known example of recursion are fractals, for example, the Sierpiński carpet – shapes repeat themselves while you keep zooming in. In the context of programming, recursion represents an ability of the function to call itself from its body. In some cases, this makes your code shorter and more expressive, as you can split complex problems into sets (Russian dolls?) of simple ones.

Consider an example of a factorial function (N! in math). A factorial of a value is a multiplicative of all numbers from 1 to the given one – for example, for 3, it will be 6: 1 * 2 * 3. The following is one way to compute a factorial through recursion:

def factorial(n):
    if n == 1:
        return n

    return n * factorial(n-1)

Here, the factorial of 1 will always return 1. For any other positive...