java - 有关带有递归方法的代码的问题

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？


如果您阅读the docs on String.substring，那么您将会理解它会返回从指定字符开始并一直扩展到结尾的子字符串。由于您指定了起始字符1，并且字符从0开始编号，因此substring(1)本质上意味着“从第二个字符开始”。这样，对于嵌套调用，字符串长度仅减少一个字符。当然最终它将达到0！当您从长度为1的字符串中获取substring(1)时，它将达到0，因为对于这样的字符串，“以第二个字符开头”表示一个空子字符串。


  问题2：为什么代码需要具有“ firstChar”才能
  扭转字符串？为什么当reverseString时代码不起作用
  接受0的子字符串，而不必添加第一个字符？


好吧，这就是递归的全部内容。如果采用第一个字符，则反转字符串的其余部分，然后将该字符附加到反转的字符串剩余部分的末尾，如果不是反转的字符串，您会得到什么？

或者，如果您想做到严谨，这是光荣的事情，那么就以正确的方式做吧。让我们首先证明该函数正确反转长度为0的字符串。

反转的空字符串是空字符串本身。由于代码在输入字符串为空时会显式返回一个空字符串（顺便说一句，为清晰起见，最好将length() == 0替换为isEmpty()），这证明该函数适用于长度为0的字符串。那不是那么难，不是吗？

现在让我们证明，如果该函数适用于长度为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)。我建议您尝试执行此操作（小心奇偶长度），看看它是否有效，并证明它如何工作。