Eda Eren

February 3, 2024
  • Computer Science
  • Miscellaneous

A recursive algorithm for incrementing natural numbers

Incrementing a natural number is simple as adding 11 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 yy to y+1y + 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 yy equals 00, and if that's the case, we return 11. That is correct: 0+1=10 + 1 = 1.

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

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

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

When yy is odd (when y mod 2=1y \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 Increment(n)=n+1\text{Increment}(n) = n + 1, so we need to prove that what we return here is indeed y + 1.

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

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

Or:

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

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

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

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

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

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

2(m+1)2(m + 1)

...which is:

2m+22m + 2

We said that yy is 2m+12m + 1. And the result of our increment function returns 2m+22m + 2, which is the correct answer: y+1y + 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.