当前位置：首页 > news >正文

C语言递归函数的习题笔记

news 2026/5/12 9:38:17

字符串逆序的递归实现（C语言）

在C语言中，实现字符串逆序的递归方法是一种高效且直观的方式。递归的核心思想是将问题分解为更小的子问题：通过交换字符串的首尾字符，然后递归地处理剩余的子字符串，直到整个字符串被逆序。下面我将逐步解释算法原理，并提供完整的C语言代码实现。

递归算法原理

基本思路：
- 给定一个字符串（以null终止的字符数组），我们定义一个递归函数，接受字符串指针和两个索引参数（start和end）。
- 基本情况（base case）：如果start >= end，表示子字符串已经处理完毕（只有一个字符或空），直接返回。
- 递归步骤：交换str[start]和str[end]位置的字符，然后递归调用函数处理子字符串str[start+1]到str[end-1]。
- 通过递归调用，字符串会从两端向中心逐步交换字符，最终实现逆序。
时间复杂度：
- 每次递归调用处理两个字符，递归深度为字符串长度的一半。
- 时间复杂度为 $O(n)$，其中 $n$ 是字符串长度。

C语言代码实现

以下是完整的C语言程序，包括递归函数和主函数测试。代码使用了标准库函数strlen来计算字符串长度，确保安全处理。

#include <stdio.h> #include <string.h> // 递归函数实现字符串逆序 void reverse_recursive(char *str, int start, int end) { if (start >= end) { // 基本情况：子字符串为空或只有一个字符 return; } // 交换首尾字符 char temp = str[start]; str[start] = str[end]; str[end] = temp; // 递归处理剩余子字符串 reverse_recursive(str, start + 1, end - 1); } int main() { char str[] = "hello"; // 测试字符串 int length = strlen(str); // 计算字符串长度 // 调用递归函数，起始索引0，结束索引length-1 reverse_recursive(str, 0, length - 1); printf("逆序后的字符串: %s\n", str); // 输出结果 return 0; }

代码解释

递归函数reverse_recursive：
- 参数：str是指向字符串的指针，start是当前子字符串的起始索引，end是结束索引。
- 第3行：检查基本情况，如果start >= end，则停止递归。
- 第5-7行：交换str[start]和str[end]的字符，使用临时变量temp。
- 第9行：递归调用自身，处理从start+1到end-1的子字符串。
主函数main：
- 第14行：定义测试字符串str（可修改为其他字符串）。
- 第15行：使用strlen获取字符串长度。
- 第17行：调用递归函数，起始索引为0，结束索引为length-1（字符串最后一个字符）。
- 第18行：打印逆序后的字符串。