数据结构：栈（三）递归及实现

datastructure ：stack

在C语言中，栈是一个常用的数据结构，递归是一种在函数内部调用自身的编程技巧。

递归通常可以使用栈来实现，因为递归的本质是一个函数调用栈的过程。

下面我将为你展示在C语言中如何使用栈实现递归。

递归的概念：

递归是指函数直接或间接地调用自身。递归函数通常有两部分组成：

基本情况：当满足某个条件时，函数不再调用自身，而是直接返回结果。

递归情况：函数调用自身，并通过传入不同的参数来解决更小规模的问题，直到达到基本情况。

递归函数示例：

让我们看一个简单的递归函数示例，计算阶乘（n!）的值。

递归函数示例：

让我们看一个简单的递归函数示例，计算阶乘（n!）的值。

#include <stdio.h>

int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1; // 基本情况
    } else {
        return n * factorial(n - 1); // 递归情况
    }
}

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

在上面的例子中，factorial 函数用来计算阶乘。当 n 为 0 或 1 时，满足基本情况直接返回1，否则调用自身并传入 n-1 来解决更小规模的问题。

使用栈实现递归：

上述递归函数实际上是在调用栈中的一系列函数调用，每次调用都会在栈上分配空间保存函数的局部变量和返回地址。使用显式栈数据结构，我们可以模拟递归的过程，避免实际的函数调用，从而避免堆栈溢出（stack overflow）的问题。

以下是使用显式栈实现阶乘的示例代码：

#include <stdio.h>

#define MAX_STACK_SIZE 100

typedef struct {
    int data[MAX_STACK_SIZE];
    int top;
} Stack;

void initialize(Stack *stack) {
    stack->top = -1;
}

void push(Stack *stack, int value) {
    if (stack->top >= MAX_STACK_SIZE - 1) {
        printf("Stack overflow!\n");
        return;
    }
    stack->data[++(stack->top)] = value;
}

int pop(Stack *stack) {
    if (stack->top < 0) {
        printf("Stack underflow!\n");
        return -1;
    }
    return stack->data[(stack->top)--];
}

int factorial_iterative(int n) {
    Stack call_stack;
    initialize(&call_stack);
    push(&call_stack, n);

    int result = 1;

    while (call_stack.top >= 0) {
        int current = pop(&call_stack);

        if (current == 0 || current == 1) {
            result *= 1; // 基本情况
        } else {
            result *= current;
            push(&call_stack, current - 1); // 递归情况，模拟函数调用栈
        }
    }

    return result;
}

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

2.使用栈解决斐波那契数列

#include <stdio.h>

#define MAX_STACK_SIZE 100

typedef struct {
    int data[MAX_STACK_SIZE];
    int top;
} Stack;

void initialize(Stack *stack) {
    stack->top = -1;
}

void push(Stack *stack, int value) {
    if (stack->top >= MAX_STACK_SIZE - 1) {
        printf("Stack overflow!\n");
        return;
    }
    stack->data[++(stack->top)] = value;
}

int pop(Stack *stack) {
    if (stack->top < 0) {
        printf("Stack underflow!\n");
        return -1;
    }
    return stack->data[(stack->top)--];
}

int fibonacci_iterative(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;

    Stack call_stack;
    initialize(&call_stack);
    push(&call_stack, n);
    push(&call_stack, 1);
    push(&call_stack, 0);

    int result = 0;

    while (call_stack.top >= 0) {
        int a = pop(&call_stack);
        int b = pop(&call_stack);

        if (a <= 2) {
            result = a + b;
        } else {
            push(&call_stack, a - 1);
            push(&call_stack, a + b);
            push(&call_stack, b);
        }
    }

    return result;
}

int main() {
    int num = 10;
    int result = fibonacci_iterative(num);
    printf("Fibonacci(%d) = %d\n", num, result);
    return 0;
}

3.使用栈解决汉诺塔问题

汉诺塔问题是经典的递归问题，可以用C语言的栈递归来解决。汉诺塔问题的规则如下：给定三个柱子（A、B、C），其中A柱子上有n个盘子，这些盘子按照从上到下的顺序由小到大编号为1、2、3...n。现在的任务是将A柱子上的所有盘子移动到C柱子上，期间可以借助B柱子。并且在移动过程中，任何时刻都不能让一个较大的盘子放在较小的盘子上。

#include <stdio.h>

// 定义一个结构体表示栈中的元素
struct StackItem {
    int n; // 表示汉诺塔问题中的盘子编号
    char source; // 表示源柱子
    char target; // 表示目标柱子
    char temp; // 表示辅助柱子
};

// 定义一个栈结构体
struct Stack {
    struct StackItem items[100];
    int top;
};

// 初始化栈
void initStack(struct Stack* stack) {
    stack->top = -1;
}

// 入栈
void push(struct Stack* stack, struct StackItem item) {
    stack->top++;
    stack->items[stack->top] = item;
}

// 出栈
struct StackItem pop(struct Stack* stack) {
    struct StackItem item = stack->items[stack->top];
    stack->top--;
    return item;
}

// 汉诺塔递归函数
void hanoi(int n, char source, char target, char temp) {
    struct Stack stack;
    initStack(&stack);

    // 将初始问题压入栈中
    struct StackItem item = { n, source, target, temp };
    push(&stack, item);

    while (stack.top >= 0) {
        struct StackItem current = pop(&stack);
        n = current.n;
        source = current.source;
        target = current.target;
        temp = current.temp;

        if (n == 1) {
            printf("Move disk 1 from %c to %c\n", source, target);
        } else {
            // 将较大的问题压入栈中，注意参数顺序与初始问题相反
            struct StackItem item1 = { n - 1, temp, target, source };
            push(&stack, item1);
            // 处理当前问题
            printf("Move disk %d from %c to %c\n", n, source, target);
            // 将较大的问题压入栈中，注意参数顺序与初始问题相反
            struct StackItem item2 = { n - 1, source, temp, target };
            push(&stack, item2);
        }
    }
}

int main() {
    int n = 3; // 假设有3个盘子
    char source = 'A';
    char target = 'C';
    char temp = 'B';

    hanoi(n, source, target, temp);

    return 0;
}