在JavaScript中调用递归函数 [英] Recursive function calling in JavaScript

问题描述

我知道你在JavaScript中对函数进行递归调用时应该轻描淡写，因为你的第二次调用可能会慢10倍。

I know you should tread lightly when making recursive calls to functions in JavaScript because your second call could be up to 10 times slower.

Eloquent JavaScript 声明：

有一个重要问题：在大多数JavaScript实现中，第二个版本比第一个版本慢大约10倍。在JavaScript中，运行一个简单的循环要比多次调用函数便宜很多。

There is one important problem: In most JavaScript implementations, this second version is about 10 times slow than the first one. In JavaScript, running a simple loop is a lot cheaper than calling a function multiple times.

John Resig甚至说这是一个问题此帖子。

John Resig even says this is a problem in this post.

我的问题是：为什么使用递归这么低效？它只是特定引擎的构建方式吗？我们是否会在JavaScript中看到时间不是这样的？

My question is: Why is it so inefficient to use recursion? Is it just the way a particular engine is built? Will we ever see a time in JavaScript where this isn't the case?

推荐答案

函数调用比简单更昂贵循环由于更改堆栈和设置新上下文等所有开销。为了使递归非常有效，语言必须支持某种形式的尾部调用消除，这基本上意味着将某些类型的递归函数转换为循环。像OCaml，Haskell和Scheme这样的函数式语言可以做到这一点，但是我所知道的JavaScript实现没有这样做（除非他们都这样做，否则它只会有点用处，所以也许我们有餐饮哲学家的问题）。

Function calls are just more expensive than a simple loop due to all the overhead of changing the stack and setting up a new context and so on. In order for recursion to be very efficient, a language has to support some form of tail-call elimination, which basically means transforming certain kinds of recursive functions into loops. Functional languages like OCaml, Haskell and Scheme do this, but no JavaScript implementation I'm aware of does so (it would only be marginally useful unless they all did, so maybe we have a dining philosophers problem).

这篇关于在JavaScript中调用递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！