在JavaScript中反转一个字符串：递归与迭代的比较

Question

在JavaScript中反转一个字符串：递归与迭代的比较

6

一个月前，我接受了一些谷歌PTO成员的面试。其中一个问题是：

使用JS递归地反转一个字符串并用大O表示其运行时间

这是我的解决方案：

function invert(s){
    return (s.length > 1) ? s.charAt(s.length-1)+invert(s.substring(0,s.length-1)) : s;
}

很简单，我认为。

关于大O符号，我迅速回答说运行时间与输入成线性关系，因此是O(n)。然后他问我，如果通过迭代实现，运行时间有什么不同？

我回答说，有时编译器会将递归“翻译”成迭代（一些编程语言课程的记忆），因此在这种情况下，迭代和递归没有区别。顺便说一句，由于我没有收到关于这个问题的反馈，面试官也没有回答“好”或“不行”，所以我想知道您是否同意我的看法，或者您能否解释一下这两种实现方式可能存在的差异。

非常感谢！

- stecb

我不确定，但递归中可能会有一个调用堆栈生成开销，而在循环中则没有。 - Martin Jespersen

顺便说一句，我本来会存储 s.length 而不是访问它三次，但也许没有必要进行优化...（抱歉，我总是过早地进行优化，这是我的许多缺点之一） - Martin Jespersen

@Martin：调用堆栈的生成应该是非常小的开销。无论如何，这里的代码递归n次，它具有与迭代n次的循环相同的计算复杂度。 - Juliet

@Martin @Juliet：谢谢，那么..你们认为（除了可以存储的长度之外），从递归到迭代计算复杂度不会改变吗？ - stecb

我远非编译器/解释器专家，所以我只能根据自己使用 JavaScript 编码的经验提供一些感想（从 1997 年开始我就一直这样做，包括服务器端和 Netscape Faststrack 服务器，别问为什么;)。如果你从一开始就知道要迭代多少次，那么迭代总比递归更快。在实际生产项目中，我永远不会自己使用递归来实现字符串反转。尽管如此，我还是觉得它是一种优雅的解决方案 :) - Martin Jespersen

是的，我也这么认为...但他问我关于递归的问题，所以我不得不那样做:D...然而，我对时间复杂度不是O(n)有点困惑...我得重新看看我的Cormen书:D - stecb

2个回答

0

顺便提一下，为了使用尾递归，使编译器将您的递归实现为循环，您不能在堆栈上留下状态。为了解决这个问题，您可以将“状态”作为附加参数传递给函数：

function invert(sofar, s)
{
    return (s.length > 0) ? invert(s.charAt(s.length-1)+sofar, s.substring(0,s.length-1)) :  sofar;
}

- BrokenGlass

2

我认为大多数（如果有的话）JavaScript 引擎都不执行尾调用优化。 - jimr

没错，我只是提到了这一点，因为楼主在他的问题中提到了优化的可能性。 - BrokenGlass

你是对的@BrokenGlass。这个例子应该优化所有“可优化”的部分:D...我想他问我关于这种东西只是想知道我是否能够对opt做出任何贡献.. 顺便说一句，在这种情况下，您认为递归没有被“转换”成迭代吗？ - stecb

2

在你提供的例子中，即使从理论上讲也无法进行优化，因为你使用了 return xxx + invert(yyy)，所以编译器必须将 xxx 保留在堆栈中，递归计算 invert(yyy)，然后解开堆栈并执行加法。这就是为什么最好使用 return invert(yyy, xxx)，这样在堆栈上不会留下状态。这被称为尾递归，可以优化为循环（但对于Javascript而言不会）。 - BrokenGlass

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gareth Rees · Accepted Answer

您的解决方案在我看来是O(n²)。调用substring很可能是O(n)——典型的实现会为新字符串分配空间，然后复制子字符串。[但请参见评论。] 字符串连接+也可能是O(n)。甚至可能情况是长度length也是O(n)，但我认为这种情况相当不太可能。

您提出了编译器可以将递归转换为迭代的想法。这是正确的，但在函数式语言和Scheme之外很少实现；通常应用的唯一转换是尾递归消除。在您的代码中，递归不在尾部位置：在对invert进行递归调用之后，仍然需要计算+。因此，尾递归消除不适用于您的代码。

这意味着，invert的迭代版本必须以不同的方式实现。它可能具有相同或不同的复杂度，我们在看到它之前无法确定。