递归

递归是一种强大的编程技术，它允许函数调用自身来解决问题。递归将复杂问题分解为更小的、相似的子问题，直到达到一个可以直接解决的基准情况。

递归的基本概念

递归函数必须包含两个关键部分：

1. 基准情况（Base Case）：递归终止的条件，防止无限递归
2. 递归情况（Recursive Case）：函数调用自身，处理更小的子问题

递归的基本结构

返回类型 函数名(参数) {
    // 基准情况
    if (终止条件) {
        return 基准结果;
    }
    
    // 递归情况
    return 函数名(更小的参数);
}

简单的递归示例

阶乘计算

阶乘是递归的经典示例。n! = n × (n-1) × (n-2) × ... × 1

#include <stdio.h>

int factorial(int n) {
    // 基准情况
    if (n <= 1) {
        return 1;
    }
    
    // 递归情况
    return n * factorial(n - 1);
}

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

执行过程：

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120

斐波那契数列

斐波那契数列：F(n) = F(n-1) + F(n-2)，其中 F(0) = 0, F(1) = 1

#include <stdio.h>

int fibonacci(int n) {
    // 基准情况
    if (n <= 1) {
        return n;
    }
    
    // 递归情况
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n = 10;
    printf("斐波那契数列前%d项:\n", n);
    for (int i = 0; i < n; i++) {
        printf("%d ", fibonacci(i));
    }
    printf("\n");
    return 0;
}

递归的应用场景

1. 数组求和

#include <stdio.h>

int arraySum(int arr[], int size) {
    // 基准情况
    if (size == 0) {
        return 0;
    }
    
    // 递归情况
    return arr[size - 1] + arraySum(arr, size - 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("数组元素之和: %d\n", arraySum(arr, size));
    return 0;
}

2. 查找数组最大值

#include <stdio.h>

int findMax(int arr[], int size) {
    // 基准情况
    if (size == 1) {
        return arr[0];
    }
    
    // 递归情况
    int maxRest = findMax(arr, size - 1);
    return (arr[size - 1] > maxRest) ? arr[size - 1] : maxRest;
}

int main() {
    int arr[] = {3, 7, 2, 9, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("数组最大值: %d\n", findMax(arr, size));
    return 0;
}

3. 字符串反转

#include <stdio.h>
#include <string.h>

void reverseString(char str[], int start, int end) {
    // 基准情况
    if (start >= end) {
        return;
    }
    
    // 交换字符
    char temp = str[start];
    str[start] = str[end];
    str[end] = temp;
    
    // 递归情况
    reverseString(str, start + 1, end - 1);
}

int main() {
    char str[] = "Hello World";
    printf("原字符串: %s\n", str);
    reverseString(str, 0, strlen(str) - 1);
    printf("反转后: %s\n", str);
    return 0;
}

4. 判断回文

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isPalindrome(char str[], int start, int end) {
    // 基准情况
    if (start >= end) {
        return true;
    }
    
    // 如果首尾字符不匹配
    if (str[start] != str[end]) {
        return false;
    }
    
    // 递归情况
    return isPalindrome(str, start + 1, end - 1);
}

int main() {
    char str1[] = "racecar";
    char str2[] = "hello";
    
    printf("\"%s\" 是回文吗? %s\n", str1, 
           isPalindrome(str1, 0, strlen(str1) - 1) ? "是" : "否");
    printf("\"%s\" 是回文吗? %s\n", str2, 
           isPalindrome(str2, 0, strlen(str2) - 1) ? "是" : "否");
    return 0;
}

5. 汉诺塔问题

汉诺塔是递归的经典问题，将n个盘子从源柱子移动到目标柱子，借助辅助柱子。

#include <stdio.h>

void hanoi(int n, char from, char to, char aux) {
    // 基准情况
    if (n == 1) {
        printf("将盘子 1 从 %c 移动到 %c\n", from, to);
        return;
    }
    
    // 递归情况
    // 将n-1个盘子从源柱子移动到辅助柱子
    hanoi(n - 1, from, aux, to);
    
    // 将第n个盘子从源柱子移动到目标柱子
    printf("将盘子 %d 从 %c 移动到 %c\n", n, from, to);
    
    // 将n-1个盘子从辅助柱子移动到目标柱子
    hanoi(n - 1, aux, to, from);
}

int main() {
    int n = 3;
    printf("汉诺塔问题（%d个盘子）的解法:\n", n);
    hanoi(n, 'A', 'C', 'B');
    return 0;
}

6. 二分查找

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int target) {
    // 基准情况：未找到
    if (left > right) {
        return -1;
    }
    
    int mid = left + (right - left) / 2;
    
    // 基准情况：找到目标
    if (arr[mid] == target) {
        return mid;
    }
    
    // 递归情况
    if (arr[mid] > target) {
        return binarySearch(arr, left, mid - 1, target);
    } else {
        return binarySearch(arr, mid + 1, right, target);
    }
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    
    int result = binarySearch(arr, 0, size - 1, target);
    if (result != -1) {
        printf("元素 %d 在数组中的索引: %d\n", target, result);
    } else {
        printf("元素 %d 不在数组中\n", target);
    }
    return 0;
}

7. 最大公约数（GCD）

使用欧几里得算法计算最大公约数。

#include <stdio.h>

int gcd(int a, int b) {
    // 基准情况
    if (b == 0) {
        return a;
    }
    
    // 递归情况
    return gcd(b, a % b);
}

int main() {
    int num1 = 48, num2 = 18;
    printf("%d 和 %d 的最大公约数: %d\n", num1, num2, gcd(num1, num2));
    return 0;
}

8. 幂运算

#include <stdio.h>

double power(double base, int exponent) {
    // 基准情况
    if (exponent == 0) {
        return 1;
    }
    
    // 处理负指数
    if (exponent < 0) {
        return 1.0 / power(base, -exponent);
    }
    
    // 递归情况
    double half = power(base, exponent / 2);
    
    if (exponent % 2 == 0) {
        return half * half;
    } else {
        return base * half * half;
    }
}

int main() {
    double base = 2.0;
    int exponent = 10;
    printf("%.2f 的 %d 次方: %.2f\n", base, exponent, power(base, exponent));
    return 0;
}

尾递归

尾递归是指递归调用是函数中的最后一个操作。尾递归可以被编译器优化为循环，避免栈溢出。

普通递归阶乘

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);  // 不是尾递归，因为乘法在递归调用之后
}

尾递归阶乘

#include <stdio.h>

int factorialHelper(int n, int accumulator) {
    // 基准情况
    if (n <= 1) {
        return accumulator;
    }
    
    // 递归情况（尾递归）
    return factorialHelper(n - 1, n * accumulator);
}

int factorial(int n) {
    return factorialHelper(n, 1);
}

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

递归 vs 迭代

递归实现

int factorialRecursive(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorialRecursive(n - 1);
}

迭代实现

int factorialIterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

优缺点对比

特性	递归	迭代
代码简洁性	简洁优雅	相对复杂
理解难度	容易理解	需要跟踪状态
内存使用	栈空间较大	内存效率高
执行效率	可能有函数调用开销	通常更快
适用场景	树形结构、分治问题	线性问题、性能敏感

递归的注意事项

1. 栈溢出

递归深度过大会导致栈溢出。

// 危险：可能导致栈溢出
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// 对于很大的n，这会导致栈溢出
factorial(10000);  // 可能崩溃

2. 性能问题

某些递归算法效率低下，如斐波那契数列的简单实现。

// 低效的实现：重复计算
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// 优化：使用记忆化
#include <stdio.h>

#define MAX 100

int memo[MAX];

void initMemo() {
    for (int i = 0; i < MAX; i++) {
        memo[i] = -1;
    }
}

int fibonacciMemo(int n) {
    if (n <= 1) return n;
    
    if (memo[n] != -1) {
        return memo[n];
    }
    
    memo[n] = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
    return memo[n];
}

int main() {
    initMemo();
    printf("斐波那契数列第50项: %d\n", fibonacciMemo(50));
    return 0;
}

3. 必须有基准情况

没有基准情况会导致无限递归。

// 错误：没有基准情况
int infiniteRecursion(int n) {
    return infiniteRecursion(n - 1);  // 永远不会停止
}

// 正确：有基准情况
int correctRecursion(int n) {
    if (n <= 0) return 0;  // 基准情况
    return n + correctRecursion(n - 1);
}

递归的高级应用

1. 全排列

#include <stdio.h>
#include <string.h>

void swap(char *a, char *b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}

void permute(char str[], int l, int r) {
    // 基准情况
    if (l == r) {
        printf("%s\n", str);
        return;
    }
    
    // 递归情况
    for (int i = l; i <= r; i++) {
        swap(&str[l], &str[i]);
        permute(str, l + 1, r);
        swap(&str[l], &str[i]);  // 回溯
    }
}

int main() {
    char str[] = "ABC";
    printf("字符串 \"%s\" 的全排列:\n", str);
    permute(str, 0, strlen(str) - 1);
    return 0;
}

2. 二叉树遍历

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

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int data) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 前序遍历
void preorder(TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

// 中序遍历
void inorder(TreeNode* root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

// 后序遍历
void postorder(TreeNode* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("前序遍历: ");
    preorder(root);
    printf("\n");

    printf("中序遍历: ");
    inorder(root);
    printf("\n");

    printf("后序遍历: ");
    postorder(root);
    printf("\n");

    return 0;
}

3. 快速排序

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    // 基准情况
    if (low < high) {
        // 分区
        int pi = partition(arr, low, high);
        
        // 递归排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("排序前: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    quickSort(arr, 0, size - 1);

    printf("排序后: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

总结

递归是一种强大的编程技术，具有以下特点：

优点：

• 代码简洁、优雅
• 适合处理树形结构和分治问题
• 更接近数学定义
• 易于理解和维护

缺点：

• 可能导致栈溢出
• 函数调用开销较大
• 某些情况下性能不如迭代
• 需要仔细设计基准情况

适用场景：

• 树和图的遍历
• 分治算法（如快速排序、归并排序）
• 数学问题的递归定义
• 回溯算法
• 动态规划

掌握递归对于成为一名优秀的程序员非常重要，它能够帮助你以更抽象和优雅的方式解决复杂问题。