047. 理解递归与循环的转换

在C语言中，递归和循环是两种常用的控制结构，它们可以实现类似的功能，但实现方式和适用场景有所不同。理解递归与循环的转换对于优化代码和解决复杂问题非常重要。

1. 递归与循环的基本概念

递归

递归是一种函数调用自身的技术，通常用于解决可以分解为更小子问题的问题。递归函数需要满足两个条件：

递归终止条件：用于结束递归调用的条件。
递归关系：将问题分解为更小的子问题，并调用自身解决这些子问题。

递归的优点是代码简洁、逻辑清晰，但缺点是可能会导致栈溢出（递归调用过深）和性能开销（函数调用的开销）。

循环

循环是一种重复执行某段代码直到满足某个条件的控制结构。常见的循环结构包括 for、while 和 do-while 循环。循环的优点是效率高、占用内存少，但缺点是代码可能不如递归直观。

2. 递归与循环的转换

许多递归问题可以通过循环来实现，反之亦然。以下是一些常见的递归与循环转换的例子。

示例1：计算阶乘

递归实现

#include <stdio.h>

// 递归计算阶乘
long long factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main() {
    int n;
    printf("请输入一个非负整数：");
    scanf("%d", &n);
    printf("%d 的阶乘是：%lld\n", n, factorial(n));
    return 0;
}

循环实现

#include <stdio.h>

// 循环计算阶乘
long long factorial(int n) {
    long long result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

int main() {
    int n;
    printf("请输入一个非负整数：");
    scanf("%d", &n);
    printf("%d 的阶乘是：%lld\n", n, factorial(n));
    return 0;
}

示例2：汉诺塔问题

递归实现

#include <stdio.h>

// 递归解决汉诺塔问题
void hanoi(int n, char fromPeg, char toPeg, char auxPeg) {
    if (n == 1) {
        printf("将盘子 1 从 %c 移动到 %c\n", fromPeg, toPeg);
        return;
    }
    hanoi(n - 1, fromPeg, auxPeg, toPeg);
    printf("将盘子 %d 从 %c 移动到 %c\n", n, fromPeg, toPeg);
    hanoi(n - 1, auxPeg, toPeg, fromPeg);
}

int main() {
    int n;
    printf("请输入盘子的数量：");
    scanf("%d", &n);
    hanoi(n, 'A', 'C', 'B');
    return 0;
}

循环实现 汉诺塔问题的循环实现相对复杂，因为其递归逻辑较难直接转换为循环。但可以通过栈来模拟递归调用，实现非递归版本。以下是简化版的非递归实现：

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

// 非递归解决汉诺塔问题
void hanoi(int n) {
    int stack[n + 1];
    int top = 0;
    stack[top++] = n;

    while (top > 0) {
        int current = stack[--top];
        if (current == 1) {
            printf("将盘子 1 从 A 移动到 C\n");
        } else {
            stack[top++] = current - 1;
            stack[top++] = current;
            stack[top++] = current - 1;
        }
    }
}

int main() {
    int n;
    printf("请输入盘子的数量：");
    scanf("%d", &n);
    hanoi(n);
    return 0;
}

3. 递归与循环的适用场景

递归：

适用于问题可以自然分解为更小的子问题。
代码更简洁，逻辑更清晰。
但需要注意递归深度，避免栈溢出。

循环：

适用于需要重复执行某段代码的场景。
效率更高，占用内存更少。
但代码可能不如递归直观。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)