[解決済み] c++のコードを理解する。再帰性を利用したハノイの塔

質問

C++で再帰について学んでいるのですが、ハノイの塔の問題を解くために使われる以下のC++のコードでつまづいています。

void Hanoi(int m, string start, string middle, string end){
    cout << "m is equal to: " << m << endl;
    if(m == 1){
        cout << "Move Disc " << " from " << start << "  to " << end << endl;
    }
    else{
        Hanoi(m-1,start,end,middle);
        cout << "Move disc " << m << " from " << start << " to " << end << endl;
        Hanoi(m-1,middle,start,end);
    }
}
int main(){
    int discs = 3;
    Hanoi(discs, "start","middle","end");

} 

を実行すると、次のような出力が得られます。

m is equal to: 3
m is equal to: 2
m is equal to: 1
Move Disc  from start  to end
Move disc 2 from start to middle
m is equal to: 1
Move Disc  from end  to middle
Move disc 3 from start to end
m is equal to: 2
m is equal to: 1
Move Disc  from middle  to start
Move disc 2 from middle to end
m is equal to: 1
Move Disc  from start  to end

私の一般的な問題は、再帰がどのように機能しているのか理解できていないことです。

どのように解決するのですか？

これをツリーとして印刷すると、次のようになります。

main
  |--> hanoi(3, ...)
  |      |
  |      |--> hanoi(2, ...)
  |      |     |
  |      |     |--> hanoi(1, ...)
  |      |     |--> hanoi(1, ...)
  |      |<----|
  |      |--> hanoi(2, ...)
  |      |     |
  |      |     |--> hanoi(1, ...)
  |      |     |--> hanoi(1, ...)
  |      |<----|
  |<-----|
  |

を呼び出すごとに hanoi(m, ...) 最初の呼び出しでは，mが1になるまで，再びcall hanoi(m - 1, ...) ...を呼び出します．

つまり、mが2のときに逆行すると、hanoi(1, ...)を2回連続で呼び出すことになります。

   hanoi(2, ...)
      hanoi(1, ...)
      hanoi(1, ...)

mが3のとき、hanoi(2, ...)を2回連続で呼び出すことになる。

hanoi(3, ...)
   hanoi(2, ...)
      hanoi(1, ...)
      hanoi(1, ...)
   hanoi(2, ...)
      hanoi(1, ...)
      hanoi(1, ...)