数据结构 | leejkee

栈和递归

LIFO 后进先出

递归调用

需要有一个结束递归的条件，否则会持续创建栈，直到栈溢出。

拆解出递归表达式
手动维护每次调用前的状态记录，调用后的状态恢复

计算n的阶乘

递归表达式

f(n) = n * f(n-1)

每次调用需要：

f(n-1)的值
n的值

f(n-1)的值返回给调用者f(n)，而f(n-1)的值由f(n-2) * (n - 1)得来

于是发现，要么f(n-1)需要计算不知道，要么就是知道f(n-1)

flowchart LR
    %% 定义不同指令的颜色和样式，方便视觉区分
    classDef callTask fill:#e1f5fe,stroke:#0288d1,stroke-width:2px,color:#000
    classDef multTask fill:#fff3e0,stroke:#f57c00,stroke-width:2px,color:#000
    classDef emptyStack fill:#f5f5f5,stroke:#9e9e9e,stroke-width:2px,stroke-dasharray: 5 5,color:#000

    subgraph S1 [1. 初始状态]
        A1[Call 3]:::callTask
    end

    subgraph S2 [2. 压入 n=3 的拆解]
        B1[Call 2]:::callTask
        B2[Mult 3]:::multTask
        %% 使用无向连线将它们在视觉上堆叠在一起
        B1 --- B2
    end

    subgraph S3 [3. 压入 n=2 的拆解]
        C1[Call 1]:::callTask
        C2[Mult 2]:::multTask
        C3[Mult 3]:::multTask
        C1 --- C2 --- C3
    end

    subgraph S4 [4. Call 1 触底出栈]
        D1[Mult 2]:::multTask
        D2[Mult 3]:::multTask
        D1 --- D2
    end

    subgraph S5 [5. Mult 2 计算出栈]
        E1[Mult 3]:::multTask
    end

    subgraph S6 [6. 最终完成]
        F1[空栈]:::emptyStack
    end

    %% 定义步骤之间的流转和状态更新
    S1 -->|Pop Call 3| S2
    S2 -->|Pop Call 2| S3
    S3 -->|Pop Call 1\n更新 ret = 1| S4
    S4 -->|Pop Mult 2\n更新 ret = 2| S5
    S5 -->|Pop Mult 3\n更新 ret = 6| S6

// 定义指令类型
enum class TaskType {
    Call,       // 需要继续向下递归的计算指令
    Multiply    // 向上回溯时的乘法指令
};

// 定义指令结构体
struct Task {
    TaskType type;
    int n;
};

int calculate_factorial(int n) {
    std::stack<Task> task_stack;
    task_stack.push({TaskType::Call, n}); // 初始压入第一条指令
    
    int return_value = 1; // 模拟 CPU 寄存器，存放子任务的返回值

    while (!task_stack.empty()) {
        Task current_task = task_stack.top();
        task_stack.pop();

        if (current_task.type == TaskType::Call) {
            if (current_task.n == 1) {
                // 遇到 n=1，直接返回 1，不再产生新指令
                return_value = 1; 
            } else {
                // 注意压栈顺序：先压入稍后执行的乘法，再压入立即执行的下一层 Call
                task_stack.push({TaskType::Multiply, current_task.n});
                task_stack.push({TaskType::Call, current_task.n - 1});
            }
        } else if (current_task.type == TaskType::Multiply) {
            // 执行乘法指令，更新返回值寄存器
            return_value = current_task.n * return_value;
        }
    }

    return return_value;
}