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

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

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

递归算法原理

1. 基本思路：

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

2. 时间复杂度：

   • 每次递归调用处理两个字符，递归深度为字符串长度的一半。
   • 时间复杂度为 $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行：打印逆序后的字符串。

运行示例

• 输入字符串："hello"
• 输出："olleh"

注意事项

• 本实现直接修改原字符串，不需要额外空间（原地操作）。
• 确保字符串以null终止，否则可能引发错误。
• 如果字符串为空或只有一个字符，递归会直接返回，不影响结果。
• 您可以修改str的值来测试不同字符串，例如char str[] = "world".