算法之美-用状态机消除递归

高级算法思想必备

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 ，给定输入“开门”，那么下一个状态时可以运算出来的。

自动门有两个状态，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(5) << std::endl;
    return 0;
}

上述代码就是使用状态机对递归进行消除，我们可以对比一下递归版的阶乘和递推版的阶乘，以及使用状态机版的阶乘。

可以观察到，在递归逻辑较简单的时候，我们一般是将递归化为递推，在递归逻辑较复杂时，我们可以使用状态机来消除递归，虽然代码量稍大，但在某些情况(如很难推算出递推式，或者无法推出递推式)则能很好的简化递归。