C++奇技淫巧：通過無腦字元串替換的方法，來把一個遞歸函數改寫成非遞歸函數

首先聲明，學會了這個對你們的C++編程知識沒有任何幫助，還有可能走火入魔，初學者自行關閉瀏覽器（逃

• 如果函數裡面有一些定義在大括弧裡面的變數的話，先改寫成所有變數都放在最前面的形式，就像C預言所要求的一樣。如果變數類型剛好沒有預設構造函數的話，自己想辦法（逃

• 如果有返回值，改寫成通過最後一個指針參數返回，反正遞歸函數必須返回void類型。
• 如果你有一個循環體遞歸調用了自己的話，把循環改成goto。

這裡的例子是一個中序遍歷函數

struct Tree{ int data; unique_ptr<Tree> left; unique_ptr<Tree> right;};void PrintTree(const unique_ptr<Tree>& tree){ if (tree->left) { PrintTree(tree->left); } cout << tree->data << " "; if (tree->right) { PrintTree(tree->right); }}

2、把所有的變數都放在一個struct裡面，額外加上_var_state。當然在這裡，只有tree一個變數。

struct PrintTreeVariables{ const unique_ptr<Tree>& tree; int _var_state;};

3、把固定的代碼插入到函數的最前面和最後面，並在所有遞歸調用的地方標記上數字，下標從1開始。

void PrintTree(const unique_ptr<Tree>& tree){/* 最前面的代碼，要在正確的位置寫上函數的參數 */ stack<PrintTreeVariables> _var_stack; { PrintTreeVariables _var{ tree, -1 }; _var_stack.push(_var); } int _var_state = 0;_var_func_begin:switch (_var_state){case -1:; return;case 0:;/* 剛才的函數體，所有的遞歸已經被標記上了數字 */ if (tree->left) { PrintTree(tree->left); /* 1 */ } cout << tree->data << " "; if (tree->right) { PrintTree(tree->right); /* 2 */ }/* 最後面的代碼 */}_var_state = _var_stack.top()._var_state;_var_stack.pop();goto _var_func_begin;}

4、在所有的數字標記的地方插入固定的代碼：「case <數字>:;」

void PrintTree(const unique_ptr<Tree>& tree){/* 最前面的代碼 */ stack<PrintTreeVariables> _var_stack; { PrintTreeVariables _var{ tree, -1 }; _var_stack.push(_var); } int _var_state = 0;_var_func_begin:switch (_var_state){case -1:; return;case 0:;/* 剛才的函數體，所有的遞歸已經被標記上了數字 */ if (tree->left) { PrintTree(tree->left); /* 1 */case 1:; } cout << tree->data << " "; if (tree->right) { PrintTree(tree->right); /* 2 */case 2:; }/* 最後面的代碼 */}_var_state = _var_stack.top()._var_state;_var_stack.pop();goto _var_func_begin;}

5、這就是最有意思的一步了：

a) 把所有的變數的使用都在前面加上"_var_stack.top()."

b) 把所有的return語句都改成函數的最後三行代碼。當然這裡有一個缺陷，如果原本函數的循環剛好垮了case，那麼使用了break語句就會在這裡傻逼。這就是為什麼有文章開頭的條件。

c) 把所有的遞歸調用

PrintTree(x)

都替換成這樣的代碼（要在正確的位置寫上函數的參數）：

{ PrintTreeVariables _var{ x, <數字> }; _var_stack.push(_var); _var_state = 0; goto _var_func_begin;}

這個數字就是我們給出來的標記，然後函數會變成這樣：

void PrintTree(const unique_ptr<Tree>& tree){ stack<PrintTreeVariables> _var_stack; { PrintTreeVariables _var{ tree, -1 }; _var_stack.push(_var); } int _var_state = 0;_var_func_begin: switch (_var_state) { case -1:; return; case 0:; if (_var_stack.top().tree->left) { { PrintTreeVariables _var{ _var_stack.top().tree->left, 1 }; _var_stack.push(_var); _var_state = 0; goto _var_func_begin; } case 1:; } cout << _var_stack.top().tree->data << " "; if (_var_stack.top().tree->right) { { PrintTreeVariables _var{ _var_stack.top().tree->right, 2 }; _var_stack.push(_var); _var_state = 0; goto _var_func_begin; } case 2:; } } _var_state = _var_stack.top()._var_state; _var_stack.pop(); goto _var_func_begin;}

6、F5運行！

推薦閱讀：