使用狀態機消除遞歸

1. 递归的简介#

我們知道，遞歸是一種函數調用自身的方法，利用計算機程序運行的天然機制 (即計算機擅長的是解決同一個問題)，可以大幅度的精簡代碼，比如使用遞歸實現一個階乘：

long long factorial(int n) {
    if(n == 1) return 1; // 遞歸基(出口)
    return n * factorial(n - 1);
}

2. 遞歸的效率#

因為遞歸使用的是系統內存的堆棧來實現，在調用函數時，需要將函數的參數和函數的返回地址壓入堆棧中，所以在調用遞歸函數時，會產生一定的開銷，主要開銷是用來保存上一次的函數調用現場 (運行狀態和變量值)，所以，當調用次數過多時，會佔用大量的棧空間，可能導致棧溢出的問題，所以，在單純的討論效率問題上，遞歸並不是一個很好的設計模式。

3. 常見的遞歸算法#

常見的遞歸算法有很多，主要是分為兩個策略分而治之和減而治之。

所謂分而治之，就是求解一個大規模的問題，可以將其劃分為多個（通常情況下為兩個）子問題，兩個問題的規模大體相同。由子問題的解，得到原問題的解。

// 二分求和
int sum(int A[], int low, int high)
{
return (low == high) ? A[low] : sum(A, low, (low + high) >> 1) + sum(A, ((low + high) >> 1) + 1, high);
}

所謂減而治之，就是求解一個大規模的問題，可以將其劃分為兩個子問題，其一是平凡問題，另一個 / 規模縮減。由子問題的解，得到原問題的解。

// 递归求数组和
int sum(int A[], int n)
{
    return (n < 1) ? 0 : A[n - 1] + sum(A, n-1);
}

如歸併排序、快速排序以及搜索等算法就是使用的分而治之的策略。

我們也觀察到，使用遞歸對於簡化問題的效果是極好的，但同時增加了資源的開銷，所以，我們在設計算法時，有一些優化方式，如：

將非尾遞歸函數變成尾遞歸函數 (可能部分語言不支持)
將遞歸的表達式 (即自頂向下) 轉化為遞推表達式 (自底向上)
使用狀態機等方法模擬遞歸從而消除遞歸

尾遞歸：
如果一個函數中所有遞歸形式的調用都出現在函數的末尾，我們稱這個遞歸函數是尾遞歸的。當遞歸調用是整個函數體中最後執行的語句且它的返回值不屬於表達式的一部分時，這個遞歸調用就是尾遞歸。尾遞歸函數的特點是在回歸過程中不用做任何操作，這個特性很重要，因為大多數現代的編譯器會利用這種特點自動生成優化的代碼。

4. 狀態機的概念#

狀態機:

狀態機是有限狀態自動機的簡稱，是現實事物運行規則抽象而成的一個數學模型。

分為兩種，一種稱為 moore 型，一種稱為 mealy 型，其主要差別在於，moore 型狀態機的輸出只由系統內部的狀態決定，而 mealy 型的輸出由輸入和系統內部的狀態共同決定。

先來解釋什麼是 “狀態”（ State ）。現實事物是有不同狀態的，例如一個自動門，就有 open 和 closed 兩種狀態。我們通常所說的狀態機是有限狀態機，也就是被描述的事物的狀態的數量是有限個，例如自動門的狀態就是兩個 open 和 closed 。

狀態機，也就是 State Machine ，不是指一台實際機器，而是指一個數學模型。說白了，一般就是指一張狀態轉換圖。例如，根據自動門的運行規則，我們可以抽象出下面這麼一個圖。

自動門有兩個狀態，open 和 closed ，closed 狀態下，如果讀取開門信號，那麼狀態就會切換為 open 。open 狀態下如果讀取關門信號，狀態就會切換為 closed 。

狀態機的全稱是有限狀態自動機，自動兩個字也是包含重要含義的。給定一個狀態機，同時給定它的當前狀態以及輸入，那麼輸出狀態時可以明確的運算出來的。例如對於自動門，給定初始狀態 closed ，給定輸入 “開門”，那麼下一個狀態時可以運算出來的。

這樣狀態機的基本定義我們就介紹完畢了。

5. 使用狀態機消除遞歸#

知道了狀態機的概念以後，我們先來回顧一下系統運行遞歸函數的過程：

遞歸過程 (自頂向下): 如果當前狀態不滿足遞歸出口條件，則不斷的遞歸過程，將當前的狀態壓入堆棧中，直到滿足遞歸出口的條件，停止遞歸。
回溯過程 (自底向上)：當遞歸樹上的一分支的遞歸狀態結束之後，不斷的進行回溯將棧中保存的內容 pop 出棧，然後計算遞歸表達式，直到棧空為止，返回最後的計算結果。

我們可以畫出狀態圖：

這樣，我們利用這個遞歸的狀態機，使用數據結構棧，而不使用系統棧，就可以完成整個遞歸的計算，這裡以遞歸計算階乘為例子：

#include <iostream>
#include <stack>

struct Data {
    int num; // 方法的參數
    int return_address; // 方法返回的地址，這裡暫時不使用
};

std::stack<Data> my_stk;

int execute_factorial(int n) {
    int state = 1; // 初始狀態為1
    int res = 1; 
    while(state != 6) { // 當狀態為6時結束遞歸
        switch(state) {
            case 1: // 遞歸初始化狀態
                state = 2;
                break;
            case 2: // 判斷是否到達遞歸出口
                if(n <= 1) {  
                    res = 1;
                    state = 4; // 遞歸過程完成，進入回溯狀態
                } else 
                    state = 3; // 繼續遞歸過程

                break;
            case 3: // 遞歸入棧
                my_stk.push({n, 0});
                --n; // 每遞歸一次n減1
                state = 2;
                break;
            case 4: // 棧是否為空
                if(my_stk.empty())
                    state = 6;
                else
                    state = 5;
                break;
            case 5: // 回溯過程
                Data tmp =my_stk.top();
                my_stk.pop();
                res *= tmp.num;
                state = 4;
                break;
        }
    }
    return res;
}

int main()
{
    std::cout << execute_factorial(0) << std::endl;
    return 0;
}

上述代碼就是使用狀態機對遞歸進行消除，我們可以對比一下遞歸版的階乘和遞推版的階乘，以及使用狀態機版的階乘，可以觀察到，在遞歸邏輯較簡單的時候，我們一般是將遞歸化為遞推，在遞歸邏輯較複雜時，我們可以使用狀態機來消除遞歸，雖然代碼量稍大，但在某些情況 (如很難推算出遞推式，或者無法推出遞推式) 則能很好的簡化遞歸。