递归函数

函数的自我调用

递归函数是函数直接或间接调用自身的编程技术。东巴文（db-w.cn） 将带你深入理解递归函数,掌握递归编程的核心技能。

💡 东巴文观点：递归是将复杂问题分解为简单问题的艺术,通过函数自我调用实现问题的自我相似性解决。

递归概述

什么是递归？

东巴文说明：递归是函数直接或间接调用自身的过程。

东巴文递归结构：

递归函数
├── 基准情况（Base Case）
│   └── 终止递归的条件
├── 递归情况（Recursive Case）
│   └── 函数调用自身
└── 递归调用（Recursive Call）
    └── 向基准情况靠近

递归的基本结构

返回类型 函数名(参数) {
    if (基准情况) {
        // 返回结果,不再递归
        return 结果;
    } else {
        // 递归调用
        return 函数名(更小的参数);
    }
}

第一个递归函数

#include <stdio.h>

// 递归函数：倒数
void countdown(int n) {
    // 基准情况
    if (n <= 0) {
        printf("发射！\n");
        return;
    }
    
    // 递归情况
    printf("%d\n", n);
    countdown(n - 1);  // 递归调用
}

int main() {
    printf("=== 东巴文第一个递归函数 ===\n\n");
    
    countdown(5);
    
    return 0;
}

东巴文执行过程：

countdown(5)
  打印 5
  countdown(4)
    打印 4
    countdown(3)
      打印 3
      countdown(2)
        打印 2
        countdown(1)
          打印 1
          countdown(0)
            打印 "发射！"
            返回
          返回
        返回
      返回
    返回
  返回

递归的经典应用

1. 阶乘

#include <stdio.h>

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

// 迭代计算阶乘
long factorial_iterative(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

int main() {
    printf("=== 东巴文阶乘递归 ===\n\n");
    
    printf("递归方法：\n");
    printf("5! = %ld\n", factorial(5));
    printf("10! = %ld\n", factorial(10));
    
    printf("\n迭代方法：\n");
    printf("5! = %ld\n", factorial_iterative(5));
    printf("10! = %ld\n", factorial_iterative(10));
    
    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

2. 斐波那契数列

#include <stdio.h>

// 递归计算斐波那契数列
long fibonacci(int n) {
    // 基准情况
    if (n <= 1) {
        return n;
    }
    
    // 递归情况
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// 迭代计算斐波那契数列
long fibonacci_iterative(int n) {
    if (n <= 1) return n;
    
    long a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    printf("=== 东巴文斐波那契递归 ===\n\n");
    
    printf("递归方法：\n");
    printf("斐波那契数列前10项：\n");
    for (int i = 0; i < 10; i++) {
        printf("%ld ", fibonacci(i));
    }
    printf("\n");
    
    printf("\n迭代方法：\n");
    printf("斐波那契数列前10项：\n");
    for (int i = 0; i < 10; i++) {
        printf("%ld ", fibonacci_iterative(i));
    }
    printf("\n");
    
    return 0;
}

3. 汉诺塔

#include <stdio.h>

// 汉诺塔递归解法
void hanoi(int n, char from, char to, char aux) {
    // 基准情况
    if (n == 1) {
        printf("移动盘子1从%c到%c\n", from, to);
        return;
    }
    
    // 递归情况
    hanoi(n - 1, from, aux, to);  // 将n-1个盘子从from移到aux
    printf("移动盘子%d从%c到%c\n", n, from, to);  // 移动第n个盘子
    hanoi(n - 1, aux, to, from);  // 将n-1个盘子从aux移到to
}

int main() {
    printf("=== 东巴文汉诺塔递归 ===\n\n");
    
    printf("3个盘子的汉诺塔：\n");
    hanoi(3, 'A', 'C', 'B');
    
    return 0;
}

4. 二分查找

#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, mid + 1, right, target);  // 搜索右半部分
    } else {
        return binarySearch(arr, left, mid - 1, target);  // 搜索左半部分
    }
}

int main() {
    printf("=== 东巴文二分查找递归 ===\n\n");
    
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    int target = 7;
    int index = binarySearch(arr, 0, size - 1, target);
    
    if (index != -1) {
        printf("找到%d,位置：%d\n", target, index);
    } else {
        printf("未找到%d\n", target);
    }
    
    return 0;
}

5. 最大公约数

#include <stdio.h>

// 递归计算最大公约数（欧几里得算法）
int gcd(int a, int b) {
    // 基准情况
    if (b == 0) {
        return a;
    }
    
    // 递归情况
    return gcd(b, a % b);
}

// 迭代计算最大公约数
int gcd_iterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    printf("=== 东巴文最大公约数递归 ===\n\n");
    
    printf("递归方法：\n");
    printf("gcd(48, 18) = %d\n", gcd(48, 18));
    printf("gcd(56, 42) = %d\n", gcd(56, 42));
    
    printf("\n迭代方法：\n");
    printf("gcd(48, 18) = %d\n", gcd_iterative(48, 18));
    printf("gcd(56, 42) = %d\n", gcd_iterative(56, 42));
    
    return 0;
}

递归的优缺点

优点

东巴文递归优点表：

缺点

东巴文递归缺点表：

递归 vs 迭代

性能对比

#include <stdio.h>
#include <time.h>

// 递归计算斐波那契
long fib_recursive(int n) {
    if (n <= 1) return n;
    return fib_recursive(n - 1) + fib_recursive(n - 2);
}

// 迭代计算斐波那契
long fib_iterative(int n) {
    if (n <= 1) return n;
    
    long a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    printf("=== 东巴文递归 vs 迭代性能对比 ===\n\n");
    
    int n = 35;
    clock_t start, end;
    
    // 递归方法
    start = clock();
    long result1 = fib_recursive(n);
    end = clock();
    printf("递归方法：fib(%d) = %ld\n", n, result1);
    printf("耗时：%.3f秒\n", (double)(end - start) / CLOCKS_PER_SEC);
    
    // 迭代方法
    start = clock();
    long result2 = fib_iterative(n);
    end = clock();
    printf("\n迭代方法：fib(%d) = %ld\n", n, result2);
    printf("耗时：%.3f秒\n", (double)(end - start) / CLOCKS_PER_SEC);
    
    return 0;
}

东巴文对比表：

递归的优化

1. 尾递归优化

东巴文说明：尾递归是递归调用在函数的最后一步,编译器可以优化为迭代。

#include <stdio.h>

// 普通递归
long factorial_normal(int n) {
    if (n <= 1) return 1;
    return n * factorial_normal(n - 1);  // 不是尾递归
}

// 尾递归
long factorial_tail(int n, long accumulator) {
    if (n <= 1) return accumulator;
    return factorial_tail(n - 1, n * accumulator);  // 尾递归
}

// 包装函数
long factorial(int n) {
    return factorial_tail(n, 1);
}

int main() {
    printf("=== 东巴文尾递归优化 ===\n\n");
    
    printf("普通递归：5! = %ld\n", factorial_normal(5));
    printf("尾递归：5! = %ld\n", factorial(5));
    
    return 0;
}

2. 记忆化递归

东巴文说明：记忆化递归使用缓存存储已计算的结果,避免重复计算。

#include <stdio.h>

#define MAX_N 100

// 记忆化缓存
long cache[MAX_N] = {0};

// 记忆化递归斐波那契
long fib_memoization(int n) {
    // 基准情况
    if (n <= 1) return n;
    
    // 检查缓存
    if (cache[n] != 0) {
        return cache[n];
    }
    
    // 计算并缓存
    cache[n] = fib_memoization(n - 1) + fib_memoization(n - 2);
    return cache[n];
}

int main() {
    printf("=== 东巴文记忆化递归 ===\n\n");
    
    printf("斐波那契数列前20项：\n");
    for (int i = 0; i < 20; i++) {
        printf("%ld ", fib_memoization(i));
    }
    printf("\n");
    
    return 0;
}

3. 限制递归深度

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

#define MAX_DEPTH 1000

// 限制递归深度
int recursiveFunction(int n, int depth) {
    // 检查递归深度
    if (depth > MAX_DEPTH) {
        printf("错误：递归深度超过限制\n");
        return -1;
    }
    
    // 基准情况
    if (n <= 0) {
        return 0;
    }
    
    // 递归情况
    return n + recursiveFunction(n - 1, depth + 1);
}

int main() {
    printf("=== 东巴文限制递归深度 ===\n\n");
    
    int result = recursiveFunction(100, 0);
    printf("结果：%d\n", result);
    
    return 0;
}

递归的应用场景

1. 树的遍历

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

// 树节点
struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 创建树节点
struct TreeNode* createNode(int data) {
    struct TreeNode *node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 前序遍历（递归）
void preorderTraversal(struct TreeNode *root) {
    if (root == NULL) return;
    
    printf("%d ", root->data);  // 访问根节点
    preorderTraversal(root->left);  // 遍历左子树
    preorderTraversal(root->right);  // 遍历右子树
}

// 中序遍历（递归）
void inorderTraversal(struct TreeNode *root) {
    if (root == NULL) return;
    
    inorderTraversal(root->left);  // 遍历左子树
    printf("%d ", root->data);  // 访问根节点
    inorderTraversal(root->right);  // 遍历右子树
}

// 后序遍历（递归）
void postorderTraversal(struct TreeNode *root) {
    if (root == NULL) return;
    
    postorderTraversal(root->left);  // 遍历左子树
    postorderTraversal(root->right);  // 遍历右子树
    printf("%d ", root->data);  // 访问根节点
}

int main() {
    printf("=== 东巴文树的递归遍历 ===\n\n");
    
    // 构建树
    struct TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    
    printf("前序遍历：");
    preorderTraversal(root);
    printf("\n");
    
    printf("中序遍历：");
    inorderTraversal(root);
    printf("\n");
    
    printf("后序遍历：");
    postorderTraversal(root);
    printf("\n");
    
    return 0;
}

2. 快速排序

#include <stdio.h>

// 分区函数
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++;
            // 交换arr[i]和arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    // 交换arr[i+1]和arr[high]
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    
    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() {
    printf("=== 东巴文快速排序递归 ===\n\n");
    
    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;
}

东巴文最佳实践

1. 确保有基准情况

// ✅ 正确：有基准情况
int factorial(int n) {
    if (n <= 1) return 1;  // 基准情况
    return n * factorial(n - 1);
}

// ❌ 错误：没有基准情况
int factorial_bad(int n) {
    return n * factorial_bad(n - 1);  // 无限递归
}

2. 确保向基准情况靠近

// ✅ 正确：向基准情况靠近
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // n-1向基准情况靠近
}

// ❌ 错误：不向基准情况靠近
int factorial_bad(int n) {
    if (n <= 1) return 1;
    return n * factorial_bad(n);  // n不变,不会到达基准情况
}

3. 避免重复计算

// ❌ 错误：重复计算
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);  // 大量重复计算
}

// ✅ 正确：使用记忆化
int cache[100] = {0};
int fib_memo(int n) {
    if (n <= 1) return n;
    if (cache[n] != 0) return cache[n];
    cache[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return cache[n];
}

4. 考虑使用迭代

// 递归：代码简洁但效率低
int factorial_recursive(int n) {
    if (n <= 1) return 1;
    return n * factorial_recursive(n - 1);
}

// 迭代：效率更高
int factorial_iterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

东巴文验证清单

完成本章学习后,请确认：

• 理解递归的概念
• 掌握递归的基本结构
• 掌握递归的经典应用
• 了解递归的优缺点
• 理解递归与迭代的区别
• 掌握递归的优化方法
• 了解递归的应用场景
• 掌握递归的最佳实践

下一步学习

掌握递归函数后,你可以继续学习：

• 数组 - 学习数组的使用
• 字符串 - 学习字符串的处理
• 指针 - 学习指针的使用

如果遇到问题,欢迎访问 东巴文（db-w.cn） 获取帮助！

东巴文（db-w.cn） - 让编程学习更简单

📦 东巴文递归函数提示：递归是解决问题的优雅方式,掌握递归是成为优秀程序员的关键。在 db-w.cn,我们会通过大量实例帮你掌握递归函数的使用！