• Computer Science
• Miscellaneous

A recursive algorithm for incrementing natural numbers

Incrementing a natural number is simple as adding $1$ to it, so why would we ever want to think about a fancy way of doing it? All we need to do is to go from $y$ to $y + 1$, and well, that's pretty obvious.

But, let's take a look at one example:

from math import floor

def increment(y):
    if y == 0:
        return 1
    elif y % 2 == 1:
        return 2 * increment(floor(y / 2))

    return y + 1

from math import floor

def increment(y):
    if y == 0:
        return 1
    elif y % 2 == 1:
        return 2 * increment(floor(y / 2))

    return y + 1

It's a beautiful recursive algorithm for incrementing natural numbers, taken from Steven Skiena’s The Algorithm Design Manual.

But how do we know that it's correct?

The book answers it, by using induction.

The base case is when $y$ equals $0$, and if that's the case, we return $1$. That is correct: $0 + 1 = 1$.

Our induction hypothesis is that $\text{Increment}(n - 1)$ is $n$. We assume that is the case, and go on to show that $\text{Increment}(n)$ holds as well, that is, $\text{Increment}(n) = n + 1$.

When $y$ is an even number (when $y \text{ mod } 2 = 0$), we return $y + 1$ in the last line, so that's correct.

So what's the deal with odd numbers, then?

When $y$ is odd (when $y \text{ mod } 2 = 1$), what is returned from the increment function is:

2 * increment(floor(y / 2))

2 * increment(floor(y / 2))

Remember that we need to prove $\text{Increment}(n) = n + 1$, so we need to prove that what we return here is indeed y + 1.

When $y$ is odd, we can write it as $2m + 1$, for some integer $m$. In that case, what we have is:

2 * increment(floor(((2 * m) + 1) / 2))

2 * increment(floor(((2 * m) + 1) / 2))

Or:

$2 \cdot \text{Increment}(\lfloor(2m + 1) / 2\rfloor)$

We can simplify it by dividing the terms inside $\text{Increment}$ by $2$:

$2 \cdot \text{Increment}(\lfloor{m + 1 / 2}\rfloor)$

Taking the floor of $m + 1/2$, we have just $m$ (remember that $m$ is an integer):

$2 \cdot \text{Increment}(m)$

...which is (by our induction hypothesis):

$2(m + 1)$

...which is:

$2m + 2$

We said that $y$ is $2m + 1$. And the result of our increment function returns $2m + 2$, which is the correct answer: $y + 1$ 🎉

This is certainly a bit tricky at first, but it provides an important lesson that induction is a solid way of proving correctness, even though most of it feels like magic.

The lectures based on the book The Algorithm Design Manual can be found here.