二、递归(三)

用栈替代递归

#include "stdafx.h"
#include<iostream>
#include<stack>
using namespace std;

//非递归解法
struct problem{
    int n;
    char src, mid, dest;
    problem(int nn, char s, char m, char d) :n(nn), src(s), mid(m), dest(d){

    }
};
stack<problem>stk;

//递归解法
void Hanoi(int n, char src, char mid, char dest){
    if (n == 1){
        cout << src << "->" << dest << endl;
        return;
    }
    Hanoi(n - 1, src, dest, mid);
    cout << src << "->" << dest << endl;
    Hanoi(n - 1, mid, src, dest);
    return;
}



int main(){
    int n;
    cin >> n;
    cout << "Recursion:" << endl;
    stk.push(problem(n, 'A', 'B', 'C'));
    while (!stk.empty()){//栈不为空
        problem curPrb = stk.top(); //获取最上层问题
        stk.pop();//出栈
        if (curPrb.n == 1)cout << curPrb.src << "->" << curPrb.dest << endl;
        else
        {
            //分解子问题
            //放入第三个问题
            stk.push(problem(curPrb.n - 1, curPrb.mid, curPrb.src, curPrb.dest));
            //放入第二个问题
            stk.push(problem(1, curPrb.src, curPrb.mid, curPrb.dest));
           //放入第一个问题
            stk.push(problem(curPrb.n - 1, curPrb.src, curPrb.dest, curPrb.mid));

        }

    }
    cout << "Non-Recursion:" << endl;
    Hanoi(n, 'A', 'B', 'C');
    return 0;
}