Recursion as a Problem-Solving Technique

Recursion is a powerful approach to problem-solving, often providing a straightforward and natural implementation that aligns closely with the original problem specification, which can save considerable time and resources in development, validation, and maintenance.

But what makes recursion such an effective problem-solving technique?

Recursion can be seen as a mathematical formalization of the scientific method, as described by Descartes in his seminal work, Discourse on the Method. Specifically, it formalizes the principles of breaking down a problem into smaller parts and building a solution from these sub-solutions, as emphasized in the method's second and third parts. Software engineers will also appreciate the emphasis on understanding and ordering the problem, corresponding to the method's first and fourth parts.

To apply recursion effectively as a problem-solving technique, we:

1. Think about how to divide the problem into smaller sub-problems and write a Divide function.
2. Assume we have a solution for the sub-problems.
3. Write a Build function to combine the sub-problem solutions into a solution for the original problem.

In pseudocode:

S = Build(S(Divide))

The key insight is that recursion allows us to solve a problem by assuming we already have a solution. All we need to do is determine how to Divide and Build; the rest is handled by the recursion itself.

Does this really work? Absolutely. As Arthur C. Clarke once said, "Any sufficiently advanced technology is indistinguishable from magic." Let us explore an example.

Fast Exponentiation

Suppose you only know how to multiply, and you need to compute

$3^{16}$. An iterative approach might look like:

$$3^{16}=(((((...((3\cdot 3)\cdot 3)\cdot 3)...\cdot 3)\cdot 3)$$

This is tedious and repetitive, so a better approach is needed. Recursion offers a more elegant solution by dividing the problem:

1. Divide the computation into smaller tasks. For
   $3^{16}$, we can write:
   
   $$3^{16}=(3^8)\cdot (3^8)$$
2. Apply the same principle to
   $3^8$:
   
   $$3^8=(3^4)\cdot (3^4)$$
3. Continue dividing until we reach a base case, such as
   $3^1$.
4. Once we reach the base case, we can build the solution by multiplying the results together.

This strategy of dividing problems in half is not only effective for exponentiation but is also at the core of many efficient algorithms, making recursion a valuable tool in problem-solving, regardless of whether the final implementation is recursive or iterative.

The Towers of Hanoi

One of the classic examples of recursion is the Towers of Hanoi. Try to think of a solution that doesn't use recursion – it is a challenge worth exploring!

(By the way, why do we know that every recursive program can be transformed into an iterative one?)

To get started, solve the Towers of Hanoi puzzle online. For

$n=3$, where do you place the top disk on the first move? There's only one correct answer.

Figure 1: Initial position of the Hanoi Towers

How does the solution work for 4 disks? What is the maximum number of disks you can solve?
If you feel confident solving the puzzle with 5 or 6 disks, you might have discovered an algorithm that works for any number

$n$ of disks.

The Standard Solution

Let us start by revisiting the standard (recursive) version of the Towers of Hanoi problem.

Figure 2: Initial position of the Hanoi Towers

The principle of the recursive solution is illustrated in Figure 3 below.

Figure 3: Principle of the recursive solution: move the

$n-1$ smallest disks to an intermediate peg, move the largest disk to its destination, and then move the

$n-1$ remaining disks on top of it.

The disks are initially stacked on the first peg (denoted by D) and must be moved to the destination peg (denoted by A) in the minimum number of moves. The destination peg is on the right if the number of disks is odd, otherwise it is the middle peg. The pegs are numbered 0, 1, and 2 from left to right, and all moves are modulo 3.

It is forbidden to place a disk on top of a smaller disk. Let

$n$ represent the number of disks.

We illustrate the first moves in Figures 4 to 7.

The analysis of these first moves reveals some properties. In particular, the smallest disk always moves every second step. It moves successively across all pegs: D → A, A → I, I → D, and so on. Using the peg numbering, this corresponds to the cycling sequence: 0 → 2, 2 → 1, 1 → 0. The second smallest disk moves every four steps (e.g., steps 2, 6, etc.), and the

$i$-th smallest disk moves every

$2^i$ steps, while the largest disk moves only once. As the smallest disk's moves are predetermined, there is only one possible move left for the other disks.

Figure 4: First and second moves

Figure 5: Moves 3 and 4

Figure 6: Moves 5 and 6

Figure 7: Move 7

Coding

Coding Moves

The successive moves described earlier can be represented using binary coding. Let

$m$ denote the move index. A natural way to represent each disk is by assigning a binary digit, with the most significant (leftmost) bit representing the largest disk, as shown in Figure 8.

Figure 8: Labeling the disks using a bit string

The rule for determining which disk to move is depicted in Figure 9.

Figure 9: Position of the moved disks (left) and periodic pattern (right). The smallest disk moves every second step, while the second smallest disk moves every four steps, and so on.

More precisely, the smallest disk moves every second step (when

$m$ is odd). The other disks are determined by the number of times

$m$ can be divided by 2 (i.e., the number of trailing zero bits). The position of the disk to move is given by the rank of the first 1 bit in the binary representation of the move (see Figure 10). For instance, at move 12 (

$m={01100}_2$), the rank is 3 (the third disk is moving).

Figure 10: Binary representation of the move index

$m$ showing the disk to move (rank of the first bit at 1 from the right—in blue)

The departure and destination pegs (indexed by 0 and 2) for the

$m$-th move can also be determined elegantly using bitwise operations. Recall that the pegs are numbered 0, 1, and 2 from left to right, and the disks start stacked on peg 0. Their destination is on peg 1 or 2, depending on the parity of the number of disks. Move

$m$ is from peg

$(m\mathrm{\&}(m-1))\mathrm{mod}3$ to peg

$((m|(m-1))+1)\mathrm{mod}3$.

Coding Positions

We can also represent the positions of the disks at any given move rather than the moves themselves. The bit string is read from left to right, with each bit indicating the location of the corresponding disk:

• A 0 means that the disk is on the initial peg, while a 1 means it is on the destination peg (right peg if the number of disks is odd, middle peg otherwise).
• If a bit differs from the previous one, the corresponding disk moves one position to the left or right. Whether it moves left or right depends on the following rule: Let
  $k$ be the number of larger disks on the same peg as their next larger disk. Add 1 to
  $k$ if the largest disk is still on its initial peg. If
  $k$ is even, the disk moves to the right peg; otherwise, it moves to the left peg.

Using Gray Code

Gray code is a binary coding system where each number differs from the previous one by exactly one bit. This system can be used to describe the solution to the Towers of Hanoi.

If the moves are represented by a reflected Gray code (starting from zero), the position of the changed bit corresponds to the disk to move.

Gray code was originally invented by a French mathematician named Louis Gros in 1872 and later reinvented by Frank Gray at Bell Labs in 1930.

There are several variants of Gray codes. The most popular one is the reflected Gray code, whose construction is illustrated in Figure 15. The 1-bit Gray code consists of 0 and 1. The 2-bit Gray code is obtained by mirroring the 1-bit code and prefixing it with 0 and 1. This construction continues for higher bit codes (see Figure 15).

Figure 15: Construction of reflected Gray codes (

$n=1,2,3$).

Figure 16: From binary to reflected Gray code.

The most significant characteristic of Gray code is that only one bit changes between consecutive numbers. To determine the bit that changes from one position to the next:

• If the number of 1 bits in position
  $i$ is even, flip the last bit.
• Otherwise, flip the bit to the left of the rightmost bit equal to 1.

Gray code can easily be derived from the classical binary representation using the following steps (see Figure 16):

$$(x_{n-1}{x}_{n-2}\dots x_1{x}_0{)}_2$$

Shift right:

$$(0x_{n-1}{x}_{n-2}\dots x_1{)}_2$$

Take the exclusive OR (bitwise) between the original binary code and its shifted version:

$$(x_{n-1}(x_{n-2}\oplus x_{n-1})\dots (x_0\oplus x_1){)}_G$$

For example, the binary code of 5 (

${00101}_2$) becomes

${00111}_G$ using Gray coding.

The algorithm for generating this code is simply to form the bitwise exclusive-or (XOR) of

$i$ with

$i/2$ (integer part). The reason this works can be understood by thinking about how the carries work when you add one to a number in binary, and noticing that

$G(i)$ and

$G(i+1)$ differ in the bit position of the rightmost zero bit of

$i$ (prefixing a leading zero if necessary).

The Gray code guarantees that only one bit changes between consecutive numbers, preventing errors from intermediate states.

Figure 20: Single-bit operations for calculating the Gray code

$G(i)$ from i (a), or the inverse (b).
LSB and MSB indicate the least and most significant bits, respectively. XOR denotes exclusive-or.

the relation between Tower of Hanoi, Gray Code and Hamiltonian Path

Hanoi Graph and Hamiltonian Path
The Tower of Hanoi puzzle can be elegantly described through Hamiltonian paths. Each possible arrangement of the disks on the three pegs corresponds to a vertex in a Hanoi graph, and the allowable moves between these configurations form the edges connecting these vertices. For example, if all 3 disks are placed on peg 0 (initial peg), the configuration is denoted as "000".

Hanoi graph with 3 disks and 3 pegs

This state diagram is a visual way to understand the solution to the Tower of Hanoi. The state diagram is drawn as a triangle because this triangle is also called the Sierpinski triangle.

By the diagram, you can intuitively know that going all the way down and to the right is the 7-step shortest path solution.

Hamiltonian Path and Gray Code
An n-bit Gray code can be viewed as a Hamiltonian path on an n-dimensional hypercube, where each vertex represents a unique state, and transitions occur by changing one bit (disk move). Gray code directly corresponds to Hamiltonian paths. Each change in Gray code represents a single disk move in the Tower of Hanoi, offering an efficient way to track state transitions.

Hanoi Graph and Gray Code
Gray code provides a structured way to solve the Tower of Hanoi. Each bit represents a disk, and the bit that changes tells which disk should move. Gray code's one-bit difference naturally aligns with the rule that only one disk moves at a time.

Quiz 2 Problem C Illustration

Explaination of 2024 quiz 2 C hanoi tower problem in 3 pegs and 3 disks situation
From above techniques we can know in each step which disk should be moved

Starting from the LSB to the MSB of this binary string, the index of the first encountered '1' is the index of disk should be moved in this step. For example, in step 2 (Binary string

${00010}_2$), the disk index is 1.

To convert a Binary code to Gray code, can leverage the characteristic of Gray code to identify which numbered disk should be moved by XOR operation. Because two adjacent numbers in binary representation will differ by only one bit in their Gray code encoding.

int curr_gray = n_moves ^ (n_moves >> 1);
int prev_gray = (n_moves - 1) ^ ((n_moves - 1) >> 1);
int changed_bit = curr_gray ^ prev_gray;

After performing the XOR operation, the index of the '1' bit in changed_bit indicates which numbered disk should be moved in this step. To find the index of the disk, we can use __builtin_popcount(changed_bit - 1). The reason for using changed_bit - 1 is that it allows us to count the number of zeros to the right of the '1' in the binary representation of changed_bit more easily

int disk = __builtin_popcount(changed_bit - 1);

For example, now is step 2 (

${00010}_2$), the curr_gray =

${00011}_2$ and prev_gray =

${00001}_2$, changed_bit =

${00011}_2\oplus {00001}_2$ =

${00010}_2$ represent we should move disk 1 in this step, utilize __builtin_popcount(changed_bit - 1) we can get the disk = 1, because changed_bit - 1 =

${00001}_2$

Now that we know which disk to move at each step, The disk can be moved in clockwise (CW) and counter clockwise (CCW), the direction determined by the number of disks.

/* Set direction based on parity of number of disks */
int direction = (n_disks & 1) ? -1 /* counter-clockwise */
                                : 1; /* clockwise */

We need a peg_map to record the peg's neighbor index, peg_map[i] use 4 bits to store the

$i$ peg neighbor's index, upper 2 bits represent the peg's index in the counter clockwise position, lower 2 bits represent the peg's index in the clockwise position
In 3 disks situation

• Peg A (0) : 0x9 {
  ${10}_2,{01}_2$}
  • Counter Clockwise : Next peg index 2 (
    ${10}_2$), disk go to peg C
  • Clockwise : Next peg index 1 (
    ${01}_2$), disk go to peg B
• Peg B (1) : 0x2 {
  ${00}_2,{10}_2$}
  • Counter Clockwise : Next peg index 0 (
    ${00}_2$), disk go to peg A
  • Clockwise : Next peg index 2 (
    ${10}_2$), disk go to peg C
• Peg C (2) : 0x4 {
  ${01}_2,{00}_2$}
  • Counter Clockwise : Next peg index 1 (
    ${01}_2$), disk go to peg B
  • Clockwise : Next peg index 0 (
    ${00}_2$), disk go to peg A

/* Predefined packed mapping arrays */
const uint8_t peg_map[3] = {
    0x9, /* Peg A: {CCW -> C (2), CW -> B (1)} */ // #C01
    0x2, /* Peg B: {CCW -> A (0), CW -> C (2)} */ // #C02
    0x4  /* Peg C: {CCW -> B (1), CW -> A (0)} */ // #C03
};

By direction_index determine the disk should be moved in counter clockwise or clockwise

/* Calculate direction index: -1 -> 0 (CCW), 1 ->1 (CW) */
int direction_index = (direction + 1) / 2;

In pos record the disk's on which peg

/* Current peg of the disk */
int curr_peg = pos[disk];
int new_peg;

If disk index is 0, represent the disk moved in this step is the smallest disk, by shift we can determine the disk should be move in CCW or CW, if shift = 2 then get the upper 2 bits for CCW neighbor's index, else if shift = 0 then get the lower 2 bits for CW neighbor's index. For example, direction_index = 0 is CCW, disk 0 on peg A (0) then we can get shift = 2 and peg_map[0] = 0x9 (

${1001}_2$), (0x9 >> 2) & 0x3 = 2 (Peg C index)

if (disk == 0) {
    /* Calculate shift: direction_index=0 (CCW) -> shift2,
     * direction_index=1 (CW) -> shift0
     */
    int shift = (1 - direction_index) << 1;
    new_peg = (peg_map[curr_peg] >> shift) & 0x3; // #C05
}

If the disk index is not 0, it means the disk being moved is not the smallest one. To determine where to move it, check each peg (excluding the current peg of the disk) and find one that does not have any disk smaller than the current one, ensuring compliance with the Tower of Hanoi rules. If a peg meets this condition, move the disk to that peg.

else {
    /* Find the only peg not occupied by any smaller disk */
    bool found_new_peg = false;
    for (int p = 0; p < 3 && !found_new_peg; p++) {
        if (p == curr_peg)
            continue;

        /* Check if any smaller disk is on peg p */
        bool has_smaller = false;
        for (int d = 0; d < disk; d++) {
            if (pos[d] == p) {
                has_smaller = true;
                break;
            }
        }

        if (!has_smaller) {
            new_peg = p;
            found_new_peg = true;
        }
    }
}

Comparison with Hanoi Recursion Approach

In the recursive version, when the number of disks reaches 1, move disk 0 to the target peg. For other cases, first recursively move the disks from the source peg to the auxiliary peg, then move the disks from the auxiliary peg to the target peg. This ensures that each step follows the correct order of moves, complying with the rules of the Tower of Hanoi.

#include <stdio.h>

long long move_count = 0;

void hanoi(int n, char source, char target, char auxiliary)
{
    if (n == 1) {
        printf("Move disk 1 from %c to %c.\n", source, target);
        move_count++;
        return;
    }
    hanoi(n - 1, source, auxiliary, target);
    printf("Move disk %d from %c to %c.\n", n, source, target);
    move_count++;
    hanoi(n - 1, auxiliary, target, source);
}

int main()
{
    int num_disks = 3;

    printf("Solution for %d disks:\n", num_disks);
    hanoi(num_disks, 'A', 'C', 'B');
    printf("Total moves: %lld\n", move_count);

    return 0;
}

The output of the recursive version matches the output of the Frame-Stewart algorithm for 3 pegs and 3 disks,

$m$ is number of pegs and

$n$ is number of disks. Frame-Stewart algorithm is the optimal solution for the hanoi problems.

$$f(m,n)=\underset{1\le t<n}{min}\{2f(m,t)+f(m-1,n-t)\}$$
The concept of Frame-Stewart algorithm is similar with recursion approach, in 3 pegs and 3 disks situation (

$m=3,n=3$ ), below is the process of Frame-Stewart algorithm

1. Move the top
   $t$ disks using
   $m$ pegs to the second peg, taking
   $f(m,t)$ steps
2. Move the remaining
   $n-t$ disks using
   $m-1$ pegs to the last peg (since the second peg is unavailable), taking
   $f(m-1,n-t)$ steps
3. Move the top
   $t$ disks using
   $m-1$ pegs from the second peg to the last peg, taking
   $f(m,t)$ steps, and the process is complete

Further Study

To deepen your understanding of recursion and its applications, consider the following resources:

• The freeCodeCamp video on dynamic programming is an excellent resource that explores numerous examples of recursion as a problem-solving technique. The video also teaches dynamic programming, which is essentially a combination of recursion and memoization. It covers examples such as gridTraveller, canSum, howSum, bestSum, canConstruct, countConstruct, and allConstruct. These examples are particularly beneficial for preparing for coding interviews, as they help build a solid foundation in recursive problem-solving.
  • As an exercise, try solving these problems independently before watching the video solutions. Additionally, create your own variations like allSums to further reinforce your learning. By working through these problems, you will learn that once you have a correct recursive solution, optimizing it with memoization becomes relatively straightforward in these types of challenges.
  • The second half of the video focuses on converting recursive solutions into iterative ones using tabulation, which is an essential technique for improving time complexity and avoiding stack overflow issues.
• Techie Delight offers a comprehensive list of recursion practice problems along with detailed solutions. This resource is valuable for practicing a wide variety of problems, allowing you to strengthen your understanding of recursive algorithms and improve your coding skills.