有关具有递归方法的代码的问题

Question

我对这段代码有一些疑问

public static String reverseString( String s )
{
  if ( s.length() == 0 )
    return "";

  String firstChar = s.substring( 0, 1 );
  String reverseRest = reverseString( s.substring( 1 ) );

  String result = reverseRest + firstChar;

  return result;
}

public static void main( String[] args ) 
{
  String a = "The sky's the limit!";
  System.out.println( reverseString( a ) );
}

问题1:终止情况究竟如何运作？s.length如何等于0？

问题2:为什么代码需要"firstChar"能够反转字符串？当reverseString接收0的子字符串而不必添加第一个字符时,为什么代码不起作用？

Answer 1

问题1:终止情况究竟如何运作？s.length如何等于0？

如果您阅读了文档String.substring,那么您将理解它返回以指定字符开头并一直延伸到结尾的子字符串.由于您指定起始字符1,并且字符从0开始编号,substring(1)实质上意味着"从第二个字符开始".这样,字符串长度恰好减少了嵌套调用的一个字符.当然它最终会达到0!substring(1)从长度为1的字符串中取出时,它将达到0,因为这样的字符串"以第二个字符开头"表示空子字符串.

问题2:为什么代码需要"firstChar"能够反转字符串？当reverseString接收0的子字符串而不必添加第一个字符时,为什么代码不起作用？

嗯,这就是递归的全部意义所在.如果你把第一个字符,反向字符串的其余部分,然后该字符追加到结束反向休息的最串,你会得到如果不是颠倒字符串的？

或者,如果你想要严谨,这是一件光荣的事情,那么让我们以正确的方式去做.让我们首先证明这个函数正确地反转了长度为0的字符串.

反向的空字符串本身就是空字符串.由于代码明确地返回一个空字符串时,输入的字符串是空的(顺便说一下,好替换length() == 0用isEmpty()的清晰度),这证明了该功能适用于0长度的字符串.那不是那么难,是吗？

现在让我们证明,如果函数适用于一个length i(i >= 0)的字符串,那么它也适用于一个长度的字符串i + 1.假设s.length() == i + 1.我们取第一个角色,然后打电话reverseString( s.substring( 1 ) ).这个调用的参数是一个长度字符串,i因为它恰好比一个字符短一个字符s.由于我们假设我们的函数完全适用于长度字符串i,因此结果是字符串1(第二个)开始的字符串的正确反转子字符串.然后我们将第一个字符附加到此字符串s,从而使s长度正确反转i + 1.

我们已经证明它适用于长度0,因此根据我们的第二个证明,它必须在长度上工作得很好1.但由此可见,它也适用于长度2.依此类推......这就是你如何证明递归函数的工作原理.

现在如果你不添加第一个字符会发生什么.假设函数完美地用于较短的字符串(substring(1)),最终会得到一个字符串,缩短一个字符.字符串较短的字符串显然不会与原始字符相反,因此证明如果您只是反向substring(1)而不向结果添加任何内容,则此函数可能无法工作.

如果你传递substring(0)递归调用会发生什么？这是另一个有趣的问题.在我们的证明的第二部分中,我们假设该函数适用于较短的字符串.在这种情况下,substring(0)不是一个较短的字符串.实际上,它是原始字符串本身,因此传递substring(0)等同于传递s.所以我们的证据不再适用.而且,由于我们正在进行相同的调用,它将继续一次又一次地调用自身,直到你得到一个StackOverflowError递归变得太深的时候.

因此,整个想法的基础是将手头的任务分解成更小的部分,而substring(0)不是一个小部分.另一个有趣的任务是将字符串分成两半而不是仅仅切掉一个字符然后返回reverseString(right) + reverseString(left).我建议你尝试这样做(小心奇数/偶数长度),看它是否有效,并证明它是如何工作的.