Recursion

Recursion is a programming pattern that is useful in situations where a task can naturally be divided into several tasks of the same type, but simpler.

When a function solves a task, it can call many other functions in the process. A partial case of this is when a function calls itself. This is called recursion.

To start with something simple, let’s write a function _pow_recursion (float x, float y) that raises x to a natural power of y. In other words, multiply x by itself y times.

_pow_recursion (2, 2) = 4

_pow_recursion (2, 3) = 8

_pow_recursion (2, 4) = 16

When _pow_recursion (float x, float y) is called, execution splits into two branches:

1. If y == 0, then everything is trivial. This is called “the basis of recursion”, because it immediately produces the obvious result: _pow_recursion (float x, float 0) equals 1.

2. Otherwise, we can represent “_pow_recursion (x, y)” as “_pow_recursion (x, y+1) / x” if y is less than x, or “_pow_recursion (x, y-1) * x” if y is greater than x. In math, one would write x^y = “x * x^(y+1)” or “x * x^(y-1)” depending on the value of y. This is called a recursive step: we transform the task into a simpler action (multiplication or division by x) and a simpler call of the same task (_pow_recursion with lower y). The following steps simplify it more and more until y reaches 0.

We can also say that _pow_recursion calls itself recursively until y == 0

For example, to calculate _pow_recursion (2, 4) the recursive variant performs these steps:

_pow_recursion (2, 4) = 2 * _pow_recursion (2, 3)

_pow_recursion (2, 3) = 2 * _pow_recursion (2, 2)

_pow_recursion (2, 2) = 2 * _pow_recursion (2, 1)

_pow_recursion (2, 1) = 2 * _pow_recursion (2, 0)

_pow_recursion (2, 0) = 1

So recursion reduces a function call to a simpler one and then … to a simpler one, and so on, until the result becomes obvious.

The maximum number of nested calls (including the first one) is called “the recursion depth”. In our case, it will be exactly y.