Implicit recursion

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.

public static int[] genNums() {
  int N = 100; // how many elements to compute
  int[] A = new int[N+1];
  A[1] = 1;
  A[2] = 2;
  int k = 1;
  for(int i = 3; i < N+1; i++) {
    // (i-1)/2 is the parent of node i in the implicit recursion tree. 
    A[i] = A[(i-1)/2] * 10 + k;
    k = 3 - k; // cycle through 1 and 2
  }
  return A;
}

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:

public static int[] genNums() {
  int N = 100; // how many elements to compute
  int[] A = new int[N+1];
  int[] nums = {1,2,3};
  for(int i = 0; i < nums.length; i++) A[i+1] = nums[i];
  for(int i = 4; i < N+1; i++) {
    int k = nums[(i-1) % 3]; // Cycle through the numbers
    A[i] = A[(i-1)/3] * 10 + k; // Access the parent
  }
  return A;
}

The first couple of results are:

1
2
3
11
12
13
21
22
23
31
32
33
111
112

confirming that we are correct!