Eliminate Recursion Using State Machines

1. Introduction to Recursion#

We know that recursion is a method where a function calls itself, utilizing the natural mechanism of computer program execution (that is, computers excel at solving the same problem), which can significantly simplify the code. For example, using recursion to implement a factorial:

long long factorial(int n) {
    if(n == 1) return 1; // Base case (exit)
    return n * factorial(n - 1);
}

2. Efficiency of Recursion#

Because recursion uses the system's memory stack to implement, when calling a function, it needs to push the function's parameters and return address onto the stack. Therefore, calling a recursive function incurs some overhead, mainly used to save the previous function call context (running state and variable values). Thus, when the number of calls is excessive, it can occupy a large amount of stack space, potentially leading to stack overflow issues. Therefore, in purely discussing efficiency, recursion is not a very good design pattern.

3. Common Recursive Algorithms#

There are many common recursive algorithms, mainly divided into two strategies: divide and conquer and reduce and conquer.

The so-called divide and conquer means that to solve a large-scale problem, it can be divided into multiple (usually two) subproblems, with the two problems being roughly of the same scale. The solution to the original problem is obtained from the solutions of the subproblems.

// Binary sum
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);
}

The so-called reduce and conquer means that to solve a large-scale problem, it can be divided into two subproblems, one of which is trivial, and the other has a reduced scale. The solution to the original problem is obtained from the solutions of the subproblems.

// Recursive sum of an array
int sum(int A[], int n)
{
    return (n < 1) ? 0 : A[n - 1] + sum(A, n-1);
}

Algorithms such as merge sort, quick sort, and search use the divide and conquer strategy.

We also observe that using recursion is excellent for simplifying problems, but it also increases resource overhead. Therefore, when designing algorithms, there are some optimization methods, such as:

Transforming non-tail recursive functions into tail recursive functions (which may not be supported by some languages)
Converting recursive expressions (top-down) into iterative expressions (bottom-up)
Using state machines and other methods to simulate recursion to eliminate recursion

Tail Recursion:
If all recursive calls in a function appear at the end of the function, we call this recursive function tail recursive. When the recursive call is the last statement executed in the entire function body and its return value is not part of an expression, this recursive call is tail recursive. The characteristic of tail recursive functions is that no operations need to be performed during the return process, which is important because most modern compilers utilize this feature to automatically generate optimized code.

4. Concept of State Machines#

State Machine:

A state machine is short for finite state automaton, which is a mathematical model abstracted from the rules of operation of real-world entities.

There are two types: one is called Moore type, and the other is called Mealy type. The main difference is that the output of a Moore type state machine is determined only by the internal state of the system, while the output of a Mealy type is determined by both the input and the internal state of the system.

First, let's explain what "state" is. Real-world entities have different states. For example, an automatic door has two states: open and closed. The state machine we usually refer to is a finite state machine, meaning the number of states of the described entity is finite. For example, the states of an automatic door are two: open and closed.

A state machine, or State Machine, does not refer to an actual machine but rather to a mathematical model. In simple terms, it generally refers to a state transition diagram. For example, based on the operating rules of the automatic door, we can abstract the following diagram.

The automatic door has two states, open and closed. In the closed state, if the open signal is read, the state will switch to open. In the open state, if the close signal is read, the state will switch to closed.

The full name of a state machine is finite state automaton, and the term "automaton" also carries significant meaning. Given a state machine, along with its current state and input, the output state can be clearly computed. For example, for the automatic door, given the initial state closed and the input "open the door," the next state can be computed.

Thus, we have introduced the basic definition of a state machine.

5. Using State Machines to Eliminate Recursion#

After understanding the concept of state machines, let's first review the process of the system running a recursive function:

Recursive process (top-down): If the current state does not meet the exit condition for recursion, the recursive process continues, pushing the current state onto the stack until the exit condition for recursion is met, at which point recursion stops.
Backtracking process (bottom-up): When a branch of the recursive state on the recursion tree ends, backtracking continuously pops the contents saved in the stack until the stack is empty, returning the final computed result.

We can draw a state diagram:

In this way, we can use this recursive state machine, utilizing a data structure stack instead of the system stack, to complete the entire recursive calculation. Here, we take recursive calculation of factorial as an example:

#include <iostream>
#include <stack>

struct Data {
    int num; // Method parameter
    int return_address; // Method return address, temporarily unused
};

std::stack<Data> my_stk;

int execute_factorial(int n) {
    int state = 1; // Initial state is 1
    int res = 1; 
    while(state != 6) { // End recursion when state is 6
        switch(state) {
            case 1: // Recursive initialization state
                state = 2;
                break;
            case 2: // Check if reached the exit of recursion
                if(n <= 1) {  
                    res = 1;
                    state = 4; // Recursive process complete, enter backtracking state
                } else 
                    state = 3; // Continue recursive process

                break;
            case 3: // Push onto stack
                my_stk.push({n, 0});
                --n; // Decrease n by 1 for each recursion
                state = 2;
                break;
            case 4: // Is the stack empty?
                if(my_stk.empty())
                    state = 6;
                else
                    state = 5;
                break;
            case 5: // Backtracking process
                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;
}

The above code uses a state machine to eliminate recursion. We can compare the recursive version of factorial, the iterative version of factorial, and the state machine version of factorial. It can be observed that when the recursive logic is relatively simple, we generally convert recursion into iteration. When the recursive logic is more complex, we can use a state machine to eliminate recursion. Although the code may be slightly larger, in certain situations (such as when it is difficult to derive the iterative formula or when it cannot be derived), it can effectively simplify recursion.