029. 编写递归函数

在C语言中，递归函数是一种调用自身的函数。递归是一种强大的编程技术，适用于解决可以分解为更小子问题的问题。递归函数通常包含两个主要部分：基准情况（Base Case）和递归步骤（Recursive Step）**。

1. 基准情况

基准情况是递归函数的终止条件，用于防止无限递归。当问题规模缩小到一定程度时，基准情况被触发，递归停止。

2. 递归步骤

递归步骤是函数调用自身的过程，每次调用都试图将问题分解为更小的子问题，直到达到基准情况。

示例1：计算阶乘

计算一个非负整数的阶乘是一个经典的递归问题。阶乘的定义如下：

n!=n×(n−1)×(n−2)×…×1
0!=1

递归实现

#include <stdio.h>

// 递归函数：计算阶乘
int factorial(int n) {
    // 基准情况
    if (n == 0) {
        return 1;
    }
    // 递归步骤
    return n * factorial(n - 1);
}

int main() {
    int num;

    printf("Enter a non-negative integer: ");
    scanf("%d", &num);

    if (num < 0) {
        printf("Invalid input. Please enter a non-negative integer.\n");
    } else {
        printf("Factorial of %d is %d\n", num, factorial(num));
    }

    return 0;
}

输出结果

假设用户输入5，输出结果为：

Enter a non-negative integer: 5
Factorial of 5 is 120

示例2：计算斐波那契数列

斐波那契数列是一个经典的递归问题，定义如下：

F(0)=0
F(1)=1
F(n)=F(n−1)+F(n−2) 对于 n≥2

递归实现

#include <stdio.h>

// 递归函数：计算斐波那契数列
int fibonacci(int n) {
    // 基准情况
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    }
    // 递归步骤
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int num;

    printf("Enter a non-negative integer: ");
    scanf("%d", &num);

    if (num < 0) {
        printf("Invalid input. Please enter a non-negative integer.\n");
    } else {
        printf("Fibonacci number at position %d is %d\n", num, fibonacci(num));
    }

    return 0;
}

输出结果

假设用户输入6，输出结果为：

Enter a non-negative integer: 6
Fibonacci number at position 6 is 8

示例3：递归遍历链表

假设我们有一个链表，需要递归地遍历并打印链表中的每个元素。

定义链表节点

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

struct Node {
    int data;
    struct Node *next;
};

递归遍历链表

// 递归函数：遍历链表
void printList(struct Node *head) {
    // 基准情况
    if (head == NULL) {
        return;
    }
    // 递归步骤
    printf("%d -> ", head->data);
    printList(head->next);
}

int main() {
    // 创建链表
    struct Node *head = (struct Node *)malloc(sizeof(struct Node));
    head->data = 1;
    head->next = (struct Node *)malloc(sizeof(struct Node));
    head->next->data = 2;
    head->next->next = (struct Node *)malloc(sizeof(struct Node));
    head->next->next->data = 3;
    head->next->next->next = NULL;

    // 递归遍历链表并打印
    printList(head);
    printf("NULL\n");

    // 释放链表内存
    struct Node *current = head;
    while (current != NULL) {
        struct Node *temp = current;
        current = current->next;
        free(temp);
    }

    return 0;
}

输出结果

1 -> 2 -> 3 -> NULL

示例4：递归计算数组的和

假设我们有一个数组，需要递归地计算数组中所有元素的和。

递归实现

#include <stdio.h>

// 递归函数：计算数组的和
int sumArray(int arr[], int size) {
    // 基准情况
    if (size == 0) {
        return 0;
    }
    // 递归步骤
    return arr[size - 1] + sumArray(arr, size - 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Sum of array elements is %d\n", sumArray(arr, size));

    return 0;
}

输出结果

Sum of array elements is 15

注意事项

基准情况：确保递归函数有明确的基准情况，以防止无限递归。
递归深度：递归函数的调用深度不应过大，否则可能导致栈溢出。
效率：递归函数可能不如迭代函数高效，因为每次递归调用都会增加函数调用的开销。

通过上述示例，你可以看到如何在C语言中编写递归函数：

定义基准情况：递归函数的终止条件。
定义递归步骤：将问题分解为更小的子问题。
调用自身：递归函数在递归步骤中调用自身。

视频讲解

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