关于递归方法代码的问题

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”才能反转字符串？为什么当逆转字符串接受0的子字符串而不必添加第一个字符时，代码不起作用？

Answer 1

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

如果您阅读了String.substring上的文档，那么您将理解它返回从指定字符开始并一直延伸到末尾的子字符串。由于您指定了起始字符1，并且字符从0开始编号，因此substring（1）本质上意味着“从第二个字符开始”。这样，嵌套调用的字符串长度正好减少一个字符。当然，它最终会达到0！当您从长度为1的字符串中获取substring（1）时，它将达到0，因为对于这样的字符串，“从第二个字符开始”意味着一个空的子字符串。

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

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

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

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

现在让我们证明如果该函数适用于长度为i（i

我们已经证明了它适用于长度0，因此从我们的第二个证明可以看出，它也必须适用于长度1。但由此得出它也适用于长度2。等等，等等...这就是您证明递归函数工作的方式。

现在，如果不添加第一个字符，会发生什么。假设该函数对于较短的字符串（子字符串（1））工作正常，则最终得到的字符串将短一个字符。短一个字符的字符串显然不会与原始字符串相反，因此，如果只反转子字符串（1），而不在结果中添加任何内容，则证明此函数不可能工作。

如果在递归调用中传递子字符串（0），会发生什么？这是另一个有趣的问题。在证明的第二部分中，我们假设该函数适用于较短的字符串。在这种情况下，子字符串（0）不是较短的字符串。事实上，它是原始字符串本身，因此传递子字符串（0）相当于只传递s。所以我们的证明不再有效了。此外，由于我们正在进行相同的调用，它将继续一次又一次地调用自己，直到递归变得太深时得到一个堆栈溢出错误。

因此，整个想法是基于将手头的任务分解成更小的部分，并且子字符串（0）不是更小的部分。另一个有趣的任务是将字符串分成两半，而不是仅仅切掉一个字符，然后返回反向字符串（右）反向字符串（左）。我建议您尝试这样做（注意奇偶长度），看看它是否有效，并证明它是如何工作的。