面试题：C语言堆栈在递归函数中的应用

实现思路

首先定义一个结构体来表示堆栈中的元素，每个元素应包含用于计算阶乘的数值。
接着实现堆栈的基本操作，如初始化、入栈、出栈和检查堆栈是否为空。
在主函数中，将需要计算阶乘的初始值入栈。
然后通过循环，在堆栈不为空时，不断出栈元素，计算其阶乘，并将中间结果入栈，直到堆栈为空，此时堆栈顶部元素即为最终的阶乘结果。

代码实现

#include <stdio.h>
#include <stdlib.h>

// 定义堆栈元素结构体
typedef struct StackNode {
    int data;
    struct StackNode* next;
} StackNode;

// 定义堆栈结构体
typedef struct Stack {
    StackNode* top;
} Stack;

// 初始化堆栈
Stack* createStack() {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->top = NULL;
    return stack;
}

// 判断堆栈是否为空
int isStackEmpty(Stack* stack) {
    return stack->top == NULL;
}

// 入栈操作
void push(Stack* stack, int data) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    newNode->data = data;
    newNode->next = stack->top;
    stack->top = newNode;
}

// 出栈操作
int pop(Stack* stack) {
    if (isStackEmpty(stack)) {
        printf("Stack is empty\n");
        exit(1);
    }
    StackNode* temp = stack->top;
    int popped = temp->data;
    stack->top = stack->top->next;
    free(temp);
    return popped;
}

// 计算阶乘
int calculateFactorial(int n) {
    Stack* stack = createStack();
    push(stack, n);

    while (!isStackEmpty(stack)) {
        int num = pop(stack);
        if (num > 1) {
            push(stack, num - 1);
            push(stack, num * pop(stack));
        }
    }

    int result = pop(stack);
    free(stack);
    return result;
}

堆栈替代递归调用系统栈的原理

递归调用系统栈：在常规的递归调用中，系统会自动维护一个栈。每次函数调用时，系统将当前函数的局部变量、返回地址等信息压入栈中。当函数返回时，这些信息从栈中弹出。例如，在计算n!的递归过程中，函数会不断调用自身，将n、n - 1、n - 2等数值以及相应的返回地址等信息压入系统栈，直到n为1。然后从栈中弹出信息，逐步计算阶乘。
手动维护堆栈：在我们手动维护的堆栈实现中，通过自己定义的堆栈结构和操作函数，模拟了系统栈的行为。将需要计算阶乘的数值依次压入栈中，模拟递归调用时参数的传递；在计算过程中，通过出栈获取数值进行计算，并将中间结果再次压入栈，模拟递归调用中系统栈对中间结果的保存。最后，当堆栈为空时，栈顶元素即为最终的阶乘结果，这和递归调用结束时系统栈弹出最终结果是类似的。

测试

int main() {
    int num = 5;
    int result = calculateFactorial(num);
    printf("%d! = %d\n", num, result);
    return 0;
}

在main函数中，对calculateFactorial函数进行测试，计算5的阶乘并输出结果。

星途面试题库

面试题：C语言堆栈在递归函数中的应用

知识考点

面试题答案

实现思路

代码实现

堆栈替代递归调用系统栈的原理

测试