A recursive algorithm for incrementing natural numbers
Tags: computerscience, programming, learning
Published: 2024-02-04 14:49:55

Incrementing a natural number is simple as adding {% katex inline %} 1 {% endkatex %} 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 {% katex inline %} y {% endkatex %} to {% katex inline %} y + 1 {% endkatex %}, and well, that's pretty obvious.

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

```python
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](https://rivea0.github.io/bite-sized-math-for-cs/unit-01-proofs/induction/).

The _base case_ is when {% katex inline %} y {% endkatex %} equals {% katex inline %} 0 {% endkatex %}, and if that's the case, we return {% katex inline %} 1 {% endkatex %}. That is correct: {% katex inline %} 0 + 1 = 1 {% endkatex %}.

Our _induction hypothesis_ is that {% katex inline %} \text{Increment}(n - 1){% endkatex %} is {% katex inline %} n {% endkatex %}.
We assume that is the case, and go on to show that {% katex inline %} \text{Increment}(n) {% endkatex %} holds as well, that is, {% katex inline %} \text{Increment}(n) = n + 1 {% endkatex %}.

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

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

When {% katex inline %} y {% endkatex %} is odd (when {% katex inline %} y \text{ mod }  2 = 1 {% endkatex %}), what is returned from the `increment` function is: 

```python
2 * increment(floor(y / 2))
```

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

When {% katex inline %} y {% endkatex %} is odd, we can write it as {% katex inline %} 2m + 1 {% endkatex %}, for some integer {% katex inline %} m {% endkatex %}. In that case, what we have is:

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

Or:

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

| Note |
| :-- |
| {% katex inline %} \lfloor {% endkatex %} and {% katex inline %} \rfloor {% endkatex %} indicate the [floor function](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions). |

We can simplify it by dividing the terms inside {% katex inline %} \text{Increment} {% endkatex %} by {% katex inline %} 2 {% endkatex %}:

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

Taking the floor of {% katex inline %} m + 1/2 {% endkatex %}, we have just {% katex inline %} m {% endkatex %} (remember that {% katex inline %} m {% endkatex %} is an integer):

{% katex %} 2 \cdot \text{Increment}(m) {% endkatex %}

...which is (by our _induction hypothesis_):

{% katex %} 2(m + 1) {% endkatex %}

...which is:

{% katex %} 2m + 2 {% endkatex %}

We said that {% katex inline %} y {% endkatex %} is {% katex inline %} 2m + 1{% endkatex %}. And the result of our increment function returns {% katex inline %} 2m + 2 {% endkatex %}, which is the correct answer: {% katex inline %} y + 1 {% endkatex %} 🎉

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](https://www3.cs.stonybrook.edu/~skiena/373/videos/)_.