【前言】：

今天是力扣打卡第12天！

这道题目不是力扣上面的题目，之所以放到这里，是因为我感觉它很好，可以让我们加深对于递归的理解。

原题：逆置字符串

题目描述：

编写一个函数：reverse_string(char* string)(递归实现)
实现：将参数字符串中的字符反向排列，注意哦，不是逆序打印
要求：不能使用C语言库函数中的字符串操作函数

示例：

  

   

    

     

    
    

     

      //输入：abcdef
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //输出：fedcba
     
    
  
 

方法一：非递归解决

代码执行：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //方法一：非递归
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //自定义函数实现strlen()的功能
     
    
   

    

     

    
    

     

      int my_strlen(char* arr)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int len = 0;
     
    
   

    

     

    
    

     
	while (*arr != '\0')
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		len++;
     
    
   

    

     

    
    

     

      		arr++;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return len;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //void reverse_string(char* arr)
     
    
   

    

     

    
    

     

      //{
     
    
   

    

     

    
    

     

      // //采用双指针的方式
     
    
   

    

     

    
    

     

      // int left = 0;
     
    
   

    

     

    
    

     

      // int right = my_strlen(arr) - 1;
     
    
   

    

     

    
    

     

      // //left == right 时，翻不翻转都无所谓
     
    
   

    

     

    
    

     

      // while (left < right)
     
    
   

    

     

    
    

     

      // {
     
    
   

    

     

    
    

     

      // char tmp = arr[left];
     
    
   

    

     

    
    

     

      // arr[left] = arr[right];
     
    
   

    

     

    
    

     

      // arr[right] = tmp;
     
    
   

    

     

    
    

     

      // left++;
     
    
   

    

     

    
    

     

      // right--;
     
    
   

    

     

    
    

     

      // }
     
    
   

    

     

    
    

     

      //}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //上面实现采用的是数组下标的形式，这里不采用数组下标，采用指针解题
     
    
   

    

     

    
    

     

      void reverse_string(char* arr)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	char* left = arr;//指针left指向数组首元素
     
    
   

    

     

    
    

     
	char* right = arr + my_strlen(arr) - 1;
     
    
   

    

     

    
    

     
	while (left < right)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		char tmp = *left;
     
    
   

    

     

    
    

     

      		*left = *right;
     
    
   

    

     

    
    

     

      		*right = tmp;
     
    
   

    

     

    
    

     

      		left++;
     
    
   

    

     

    
    

     

      		right--;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	char arr[] = "abcdef";
     
    
   

    

     

    
    

     
	reverse_string(arr);
     
    
   

    

     

    
    

     
	printf("%s\n", arr);//fedcba
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

利用非递归解决本题很简单，这道题目使用递归解决反而增加难度了，所以本题只是让大家对于递归有一个更深的认知。

复杂度分析：

时间复杂度：O(N)

空间复杂度：O(1)

方法二：递归解决

代码执行：

  

   

    

     

    
    

     

      方法二：递归版本
     
    
   

    

     

    
    

     

      说明：其实像这种逆置问题，用非递归解题是非常方便的，用递归反而复杂了
     
    
   

    

     

    
    

     

      之所以用递归，是在练习递归的技巧
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
        reverse_string("abcdef")
     
    
   

    

     

    
    

     

       拆化： f reverse_string("bcde") a
     
    
   

    

     

    
    

     

       难点：将f和a交换一下，然后再逆序“bcde”，此时e后面放的是a,它根本就不知道什么时候结束,也就没办法将它看做一个字符串了
     
    
   

    

     

    
    

     

       如何解决呢？
     
    
   

    

     

    
    

     

       先把a拿出来，再将f放到原先a的位置，然后将原先g的位置放'\0'，此时“bcde”就是一个字符串了，对其逆序，然后再将a拿上来放到最后
     
    
   

    

     

    
    

     

      
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      
     
    
   

    

     

    
    

     

      //自定义函数实现strlen()的功能
     
    
   

    

     

    
    

     

      int my_strlen(char* arr)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int len = 0;
     
    
   

    

     

    
    

     
	while (*arr != '\0')
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		len++;
     
    
   

    

     

    
    

     

      		arr++;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return len;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void reverse_string(char* arr)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//找边界--字符串长度不大于1就不需要逆置了
     
    
   

    

     

    
    

     
	if (my_strlen(arr) <= 1)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	int len = my_strlen(arr);
     
    
   

    

     

    
    

     
	char tmp = *arr;//将a拿出来
     
    
   

    

     

    
    

     

      	*arr = *(arr + len - 1);//将f放到a的位置
     
    
   

    

     

    
    

     

      	*(arr + len - 1) = '\0';//将'\0'放到f的位置
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	reverse_string(arr + 1);//逆置bcde
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	*(arr + len - 1) = tmp;//最后将a放到最后
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	char arr[] = "abcdef";
     
    
   

    

     

    
    

     
	reverse_string(arr);
     
    
   

    

     

    
    

     
	printf("%s\n", arr);//fedcba
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

复杂度分析：

时间复杂度：O(N)

空间复杂度：O(N)

上面只分析了第一层递归，实在不理解的小伙伴可以将递归展开图画出来，慢慢去感受本题。

结语

今天是力扣打卡第12天！

这些天都是痛并快乐着，每天都很充实，一起加油。

咱们明天再见！ 

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/121257746