# Implicit recursion

#### Posted on September 27, 2015

##### Last updated on September 28, 2015

Suppose I ask you the following programming question:

Give me, in order, the first N integers whose only digits are $$1$$ and $$2$$. Store them in an array.

Now I’m sure you can easily produce a piece of recursive code to solve this (go ahead and try, the blog post will wait!). You will produce a recursive code with a branching factor of $$2$$ - for every recursive call, you will have one branch in which you append a $$1$$ to the current number, and another branch in which you will append the $$2$$. For $$k$$ recursion levels, you will explore at most $$2 ^ k - 1$$ nodes as that’s how many nodes a full binary tree with $$k$$ levels contains.

I will show you how to simulate this recursion using imperative code. Let’s number all the nodes of our implicit recursion tree, with $$0$$ as the root, $$1$$ for the root’s leftmost node, etc. We will imperatively construct this tree and store it in an array of length $$N$$. The observation to make is that in a recursion tree with a branching factor of $$k$$, the parent of node $$n$$ is $$\frac{n-1}{k}$$. You can prove this to yourself as an exercise!

This leads us to the following piece of code that gives an answer to the question I proposed.

Now the array A contains our integers starting at index 1.

This is the idea that’s used in constructing/traversing a binary heap too. We know that a binary heap is always a complete binary tree, so we can use this trick to move around the tree only with its array representation.

Now let’s change the question to give back the first $$N$$ integers that are made up of only $$1$$, $$2$$, and $$3$$ in lexigraphical order. Can you adopt the above solution to do it? Go ahead and try!

Here is how it would look like:

The first couple of results are:

confirming that we are correct!

Markdown SHA1: a923e0b6b63971fe8c501e76498b35a2cf51fc03