近两天在面试的时候被面试官问到如何将一个递归函数转换为非递归，脑袋卡壳，当场傻掉。现在回头思考，梦中惊醒。

终于知道面试官为何会提示我有限状态机了 ( ＿ ＿)ノ｜。

递归

递归（Recursion）的思想是分而治之（Divide and Conquer，D&C），本质是将一个问题拆分为与其有相同解法的小问题的集合，当问题缩小到一定规模时存在一个出口来避免无限分化。

递归是一种优美的实现，通常可以让代码变得更为简洁与易读，但由于大部分编程语言采用栈来实现函数调用，除非是递归中可被优化的尾递归，否则递归免不了调用栈的增长，且如果递归调用层级过深，还可能超过调用栈的指定界限，导致栈溢出（Stack Overflow）。

转换

为了将一个递归函数转化为非递归函数来避免调用栈的增长问题，我们可以模拟函数调用过程，通过在堆上实现自定义数据结构来保存函数的调用信息与状态，从而实现转换，当然，这不函数式。

一个函数调用过程一般包括以下部分：

  • 寄存器数据压栈，保存现场。

  • 返回地址压栈。一个函数的执行过程被内部的函数调用拆分为多个单元，可将其视为一个调用的返回地址作为状态的有限状态机。

  • 参数压栈（暂不考虑参数设置到寄存器中）。

  • 被调用函数执行完成，设置返回值，弹出返回地址并跳转，弹出寄存器数据恢复现场。

通过模拟以上步骤（最主要的步骤是状态与参数的压栈），即可实现一个递归函数的转换。

以面试中遇到的题目为例，这是一个求解 Hanoi 问题的函数，需要将其转换为非递归的形式。

void solveHanoi(int level, char from, char through, char to) {
    if (level <= 0) return;
    solveHanoi(level - 1, from, to, through);
    printf("%c -> %c\n", from, to);
    solveHanoi(level - 1, through, from, to);
}

以递归调用为界线进行分割，可以将该函数的实现分割为多个部分。

void solveHanoi(int level, char from, char through, char to) {

    ...

    $state = GetCurrentState();
    switch ($state) {
        case 0:
            // if (level <= 0) return;
            // solveHanoi(level - 1, from, to, through);
            ...
            $state++;
            break;
        case 1:
            // printf("%c -> %c\n", from, to);
            // solveHanoi(level - 1, through, from, to);
            ...
            $state++;
            break;
        case 2:
            // return
            ...
            break;
    }

    ...
}

结合栈来保存当前模拟的函数参数信息与状态，可以得到这样的转换后实现。

class Arg {
public:
    int level_;
    char from_;
    char through_;
    char to_;
    int state_;

    Arg(int level, char from, char through, char to) : level_(level),
                                                       from_(from), through_(through), to_(to),
                                                       state_(0) {}
};

void solveHanoi(int level, char from, char through, char to) {
    vector<Arg *> args;
    args.push_back(new Arg(level, from, through, to));
    while (!args.empty()) {
        Arg *top = args.back();
        switch (top->state_) {
            case 0:
                if (top->level_ <= 0) {
                    // return;
                    args.pop_back();
                    delete top;
                    break;
                }
                args.emplace_back(new Arg(top->level_ - 1, top->from_, top->to_, top->through_));
                top->state_++;
                break;
            case 1:
                printf("%c -> %c\n", top->from_, top->to_);
                args.emplace_back(new Arg(top->level_ - 1, top->through_, top->from_, top->to_));
                top->state_++;
                break;
            case 2:
                // return;
                args.pop_back();
                delete top;
                break;
        }
    }
}