Why doesn’t my solution to the Towers of Hanoi problem work correctly?

Question

In the classic problem of the Towers of Hanoi, you have three towers and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (i.e., each disk sits on top of an even larger one). You have the following constraints:

1. Only one disk can be moved at a time.
2. A disk is slid off the top of one tower onto another tower.
3. A disk cannot be placed on top of a smaller disk.

Write a program to move the disks from the first tower to the last using stacks.

Example1:
Input: A = [2, 1, 0], B = [], C = [] Output: C = [2, 1, 0]

Example2:
Input: A = [1, 0], B = [], C = [] Output: C = [1, 0]

Note:
A.length <= 14

I applied the "recursive leap of faith" (references near bottom) and wrote the solution

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        if (A.size() == 0) {
            return;
        }
        int base = A.front();
        A.erase(A.begin());
        hanota(A, C, B);
        C.push_back(base);
        hanota(B, A, C);
    }
};

the result is:

AddressSanitizer: DEADLYSIGNAL
=================================================================
==20==
ERROR: AddressSanitizer: 
stack-overflow on address 0x7ffc5b035f48 
(pc 0x00000031f5ee bp 0x7ffc5b036790 sp 0x7ffc5b035f50 T0) 
==20==
ABORTING

I draw a call graph

why the famous "recursive leap of faith" broken here? Is it related to improper stop condition?

For reference:

• Brian Harvey: Computer Science Logo Style
  Vol. 1 Symbolic Computing,
  Ch. 8: Practical Recursion: the Leap of Faith
• K. Schwarz, Z. Galant: Stanford CS106B
  slides on Thinking Recursively

Answer 1

The problem is that with C.push_back(base); you put a disc on stack C that through recursion may be called stack A, and that is a problem, because that disc should not be moved at this stage, yet that deeper call (that identifies that stack as A) will want to clear stack A completely, also moving that (large) disc again! As a side note, this will also lead to invalid moves: where the large disc is moved on top of a smaller disc.

This disc that is put on stack C is polluting the idea of "recursive leap of faith", as now your recursive process should somehow know which discs should not be moved.

Details

Let's just follow the process with input A={2,1,0}, B={}, C={}, until we get at a wrong manipulation:

The top-level call will remove 2 from A and make a recursive call to move {1,0} from stack A to B. When we get back from that recursive call, all is fine, and we have this state:

base: 2
A: {}, B: {1,0}, C: {}

Then 2 is appended to C:

A: {}, B: {1,0}, C: {2}

Note that this disc 2 is at its final spot and it should never have to move again.

We now make a second recursive call aiming to move {1,0} on top of C. Let's look at this second level in the recursion tree:

Second level:

At this point the local variables A, B and C are associated with the stacks as follows (which is still fine):

A: {1,0}, B: {}, C: {2}

The value 1 is removed from stack A, and we get:

base: 1
A: {0}, B: {}, C: {2}

A first recursive call is made with the aim to move that zero to stack B. We will look at that third-level call in detail:

Third level:

Again new local variables get to reference the stacks as follows:

A: {0}, B: {2}, C: {}

The 0 is removed from A, a recursive call is made that has nothing to do (fine), and 0 is appended to C, so we arrive in this state:

A: {}, B: {2}, C: {0}

Now we get at the second recursive call made at this third level, which brings us at a fourth-level call.

Fourth level:

Here the stacks are labeled as follows:

A: {2}, B: {}, C: {0}

...but that is problematic, since this would mean we want to move the 2 from stack A on top of C. This is not desired, nor is it valid.

Remember we said that disc 2 should never have to move again, yet that is what is going to happen here. Stack A should not be emptied. This disc 2 is polluting the algorithm.

We could go on and analyse the next steps that are taken, and we would not only see invalid stacks, but also see repetitions of the same states. I don't think it is worth to continue this analysis however, because we already know it went wrong at this point.

Solutions

There are several solutions to this.

You could for instance mark the discs that should not be moved in deeper recursion, but that is not a very elegant solution.

Since you are OK with doing an action like A.erase(A.begin()); which represents a non-Hanoi move (for the purpose of recursion), I suppose you could not object to doing the inverse C.insert(C.begin(), base) for the same purpose.

So change:

        C.push_back(base);
        hanota(B, A, C);

to:

        hanota(B, A, C);
        C.insert(C.begin(), base);

This is of course not representing the actual move when it happens, but that is also true for A.erase(A.begin());.

Alternative

Usually you would have to do this with performing only valid operations on the stacks, i.e. moving the disc at the top of a stack, and not artificially removing a disc at the bottom.

To make that work, it will be good to add a parameter that indicates how many discs need to be moved from A to C, so avoiding moving discs that are supposed to stay where they are (at that stage).

So:

void hanota(vector<int>& A, vector<int>& B, vector<int>& C, int n) {
    if (n == 0) {
        return;
    }
    hanota(A, C, B, n - 1);
    // Make the move (a valid Hanoi move)
    C.push_back(A.back()); 
    A.pop_back();
    hanota(B, A, C, n - 1);
}

The initial call needs to provide the total number of discs for n:

    vector<int> A = {4,3,2,1,0};
    vector<int> B;
    vector<int> C;
    hanota(A, B, C, A.size());