1. Introduction to Recursion#
We know that recursion is a method of calling a function itself, utilizing the natural mechanism of computer program execution (i.e., computers are good at solving the same problem), which can greatly simplify the code. For example, using recursion to implement a factorial:
long long factorial(int n) {
if(n == 1) return 1; // base case (exit condition)
return n * factorial(n - 1);
}
2. Efficiency of Recursion#
Because recursion uses the stack of system memory to implement, when calling a function, the function's parameters and return address need to be pushed into the stack. Therefore, when calling a recursive function, there will be some overhead, mainly used to save the previous function call context (execution state and variable values). So, when the number of calls is too large, it will occupy a large amount of stack space, which may cause stack overflow problems. Therefore, in terms of discussing efficiency issues alone, 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 "decrease and conquer".
The so-called "divide and conquer" means solving a large-scale problem by dividing it into multiple (usually two) subproblems, with roughly the same size. The solution to the original problem is obtained from the solutions to 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 "decrease and conquer" means solving a large-scale problem by dividing it into two subproblems, one of which is a trivial problem and the other is a reduced problem. The solution to the original problem is obtained from the solutions to the subproblems.
// Recursive sum of an array
int sum(int A[], int n)
{
return (n < 1) ? 0 : A[n - 1] + sum(A, n-1);
}
Merge sort, quicksort, and search algorithms use the "divide and conquer" strategy.
We also observe that using recursion is extremely effective in simplifying problems, but it also increases resource overhead. Therefore, when designing algorithms, there are some optimization methods, such as:
- Convert non-tail-recursive functions into tail-recursive functions (may not be supported in some languages).
- Convert recursive expressions (i.e., top-down) into iterative expressions (bottom-up).
- Use state machines or other methods to simulate recursion and eliminate recursion.
Tail Recursion:
If all recursive calls in a function are made at the end of the function and the return value of the recursive call is not part of an expression, the recursive function is called tail recursive. The characteristic of a tail-recursive function is that no operations need to be performed during the return process, which is important because most modern compilers can use this characteristic to automatically generate optimized code.
4. Concept of State Machines#
State Machine:
A state machine is an abbreviation for a finite-state automaton, which is a mathematical model abstracted from the running rules of real-world things.
There are two types of state machines: Moore type and 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 state machine is determined by both the input and the internal state of the system.
Let's first explain what a "state" is. Real-world things have different states. For example, an automatic door has two states: open and closed. We usually refer to a state machine as a finite state machine, which means that the number of states described by the state machine is finite. For example, the state of an automatic door is two: open and closed.
A state machine, also known as a state machine, does not refer to an actual machine, but to a mathematical model. In other words, it usually refers to a state transition diagram. For example, based on the operating rules of an 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 detected, the state will switch to open. In the open state, if the close signal is detected, the state will switch to closed.
This is a basic definition of a state machine.
5. Using State Machines to Eliminate Recursion#
Knowing the concept of state machines, let's first review the process of running a recursive function in a system:
- Recursive process (top-down): If the current state does not satisfy the exit condition of recursion, the recursive process continues, pushing the current state into the stack until the exit condition of recursion is met and the recursion stops.
- Backtracking process (bottom-up): After a branch of the recursion tree completes its recursive state, the contents saved in the stack are popped out one by one during backtracking, and then the recursive expression is calculated until the stack is empty, and the final calculation result is returned.
We can draw a state diagram:
This way, we can use this recursive state machine, use the data structure stack instead of the system stack, to complete the entire recursive calculation. Here is an example of calculating factorial using recursion:
#include <iostream>
#include <stack>
struct Data {
int num; // method parameter
int return_address; // return address of the method, not used here temporarily
};
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 the state is 6
switch(state) {
case 1: // recursive initialization state
state = 2;
break;
case 2: // check if the exit condition of recursion is reached
if(n <= 1) {
res = 1;
state = 4; // recursion process completed, enter backtracking state
} else
state = 3; // continue recursion process
break;
case 3: // push recursion into the stack
my_stk.push({n, 0});
--n; // decrease n by 1 for each recursion
state = 2;
break;
case 4: // check if the stack is 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 version using a state machine. We can observe that when the recursion logic is relatively simple, we generally convert recursion into iteration. When the recursion logic is more complex, we can use a state machine to eliminate recursion. Although the code is slightly longer, it can simplify recursion in certain situations (such as when it is difficult to deduce the iterative expression or when it is impossible to deduce the iterative expression).