记录一个递归反转字符串的过程

深藏阁楼爱情的钟 2023-06-17 10:53 7阅读 0赞

# 递归原理 #

（原文：[https://leetcode-cn.com/explore/featured/card/recursion-i/256/principle-of-recursion/1101/][https_leetcode-cn.com_explore_featured_card_recursion-i_256_principle-of-recursion_1101]）

--------------------

> 递归是一种解决问题的有效方法，在递归过程中，函数将自身作为子例程调用

你可能想知道如何实现调用自身的函数。诀窍在于，每当递归函数调用自身时，它都会将给定的问题拆解为子问题。递归调用继续进行，直到到子问题无需进一步递归就可以解决的地步。

为了确保递归函数不会导致无限循环，它应具有以下属性：

1.  一个简单的`基本案例（basic case）`（或一些案例） —— 能够不使用递归来产生答案的终止方案。
2.  一组规则，也称作`递推关系（recurrence relation）`，可将所有其他情况拆分到基本案例。

注意，函数可能会有多个位置进行自我调用。

### 示例 ###

--------------------

让我们从一个简单的编程问题开始：

> 以相反的顺序打印字符串。

你可以使用迭代的办法轻而易举地解决这个问题，即从字符串的最后一个字符开始遍历字符串。但是如何递归地解决它呢？

首先，我们可以将所需的函数定义为 `printReverse(str[0...n-1])`，其中 `str[0]` 表示字符串中的第一个字符。然后我们可以分两步完成给定的任务：

1.  `printReverse(str[1...n-1])`：以相反的顺序打印子字符串 `str[1...n-1]` 。
2.  `print(str[0])`：打印字符串中的第一个字符。

请注意，我们在第一步中调用函数本身，根据定义，它使函数递归。

下面给出了代码片段：

private static void printReverse(char [] str) {
      helper(0, str);
    }
    
    private static void helper(int index, char [] str) {
      if (str == null || index >= str.length) {
        return;
      }
      helper(index + 1, str);
      System.out.print(str[index]);
    }

# 递归练习： #

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 `char[]` 的形式给出。

不要给另外的数组分配额外的空间，你必须**[原地][Link 1]修改输入数组**、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 [ASCII][] 码表中的可打印字符：

我的解决方式： 不代表 最好的，只是做出来了而已。

class Solution {
        public void reverseString(char[] s) {
            new Solution().aReverse(s,0);
        }
        
        public void aReverse(char[] s ,int index){
           
            if(s == null || index >= s.length){
                return;
            }
           aReverse(s,index+1);
           if (index >= s.length / 2) { //2.只需要对调一半对称的就行，否则又会回调回去
                char tmp = s[index];   // 1.当走到这里说明是最后一个字符了，需要和前面的字符对调
                s[index] = s[s.length - 1 - index];
                s[s.length - 1 - index] = tmp;
            }
            
        }
    }

当时结论是：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4MTk4MTgx_size_16_color_FFFFFF_t_70][]

所以 应该还可以进一步优化。

[https_leetcode-cn.com_explore_featured_card_recursion-i_256_principle-of-recursion_1101]: https://leetcode-cn.com/explore/featured/card/recursion-i/256/principle-of-recursion/1101/
[Link 1]: https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95
[ASCII]: https://baike.baidu.com/item/ASCII
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4MTk4MTgx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191128172341851.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4MTk4MTgx,size_16,color_FFFFFF,t_70