为什么递归这么慢？ [英] Why is recursion so slow?
问题描述
递归对于编写一些函数非常棒，比如搜索树等但是哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇
是每个x计算fib 1到fib x-1的递归定义？用函数式语言进行的懒惰评估是否能够更快地使用b / b
递归版本更快？
是haskell中的递归fibonacci，速度与命令一样快解决方案
a程序语言？
def fibr（nbr）：
if nbr 1：
返回fibr（nbr-1）+ fibr（nbr-2）
如果nbr == 1：
返回1
如果nbr = = 0：
返回0
def fibf（n）：
sum = 0
a = 1
b = 1
如果n< = 2：返回1
for i in range（3，n + 1）：
sum = a + b
a = b
b =总和
返还金额
i found Clojure中的一个超高速版本：
（def fib-seq
（concat
[0 1]
（（fn rfib [ab]
（lazy-cons（+ ab）（rfib b（+ ab））））0 1）））
（defn fibx [x]
（最后（取（+ x 1）fib-seq）））
（fibx 12000）即时交付。它是否使用延迟评估？
引用slix< no ********** @ yahoo.se>：
递归对于编写一些函数非常棒，比如搜索树木
等但是哇怎么可能这么多计算斐波纳契的速度较慢 -
数字？
问题不在于''递归''本身，而在于算法：
def fibr（nbr）：
如果nbr 1：
返回fibr（nbr-1）+ fibr（nbr-2）
如果nbr == 1：
返回1
如果nbr == 0：
返回0
如果你跟踪，例如，fibr（5），你会发现你的代码需要计算fibr（4）
和fibr（3），并计算fibr（4），它需要计算fibr（3）和fibr（2）。作为
你可以看到，fibr（3），它的整个子树，计算两次。这足以使它成为指数算法，因此难以实现。幸运的是，迭代的
表格非常易读且高效。如果你必须坚持递归（比如，
也许你解决的问题不能轻易地迭代解决），我会建议你看看
''动态编程''，或者（更容易但不是
必然更好），'memoize''disgn模式。
是每个x计算fib 1到fib x-1的递归定义吗？
是 - 这就是算法所说的。 （嗯，实际上，算法说不止一次计算
，因此指数行为）。在这种情况下，memoize模式可以
帮助。
函数式语言中的懒惰评估避免了从而使递增版本更快？
递归版本？
不完全......函数式语言（或者应该）针对递归进行优化，
但是如果你编写的算法仍然是指数的，它仍然需要时间。
是haskell中的递归斐波纳契，与
a程序语言中的必要解决方案一样快？
[...]
i在Clojure中找到一个超高速的版本：
我已经看到了haskell的实现（相当令人印象深刻）。我不知道Clojure
（它是Lisp的一种方言吗？），但该代码看起来与haskell类似。如果你仔细观察，那么代码就没有递归（没有函数调用）。
haskell代码通过定义列表fib来工作。作为从0开始的列表，
并且从那里开始，每个元素是''fib''元素的总和加上元素
on' 'tail fib''）。懒惰的评估意味着你可以自己定义一个基于
的列表，但是没有递归函数调用。
干杯，
< br $> b $ b（我很难......我希望我有所了解）
-
Luis Zarrabeitia
FacultaddeMatemáticayComputación，UH
http：/ /profesores.matcom.uh.cu/~kyrie
slix写道：
< blockquote class =post_quotes>
递归对于编写一些函数非常棒，比如搜索树
等但是哇如何计算斐波纳契要慢得多 -
数字？
下面的比较与递归与迭代无关。
（这是一个常见的神话。）你（和其他人一样）正在比较
指数，O（1.6 ** n），算法与线性，O（n）算法。
def fibr（nbr）：
如果nbr 1：
返回fibr（nbr-1）+ fibr（nbr-2）
如果nbr == 1：
返回1
如果nbr == 0：
返回0
这是指数因为计算fib（n-2）两次，fib（n-3）三次，
模式，你可能是正确的！）（对于n <0，它返回None。）
如果重写迭代地，有一个堆栈，它仍然是指数。
def fibf（n）：
sum = 0
a = 1
b = 1
如果n< = 2：返回1
我在范围内（3，n + 1）：
sum = a + b
a = b
b =总和
返回金额
这是一种不同的线性算法。 fib（i），0< = i< n，仅计算一次.b
。 （它返回1表示n <0。）如果递归重写（尾部），
它仍然是线性的。
在Python中，一个用由于函数调用的成本，迭代比用递归编写的相同的算法更快。
但差异应该是乘法因素，几乎是$
$不同n的b $ b常数。 （我打算做一些实验来更好地解决这个问题。）因此，迭代编写的算法很容易编写，特别是使用for循环，通常都在Python程序中。
Terry Jan Reedy
2008年6月29日星期日凌晨1点27分，Terry Reedy< ; tj ***** @ udel.eduwrote：
>
slix写道：
< blockquote class =post_quotes>
>>
递归对于编写一些函数非常棒，比如搜索树等等但是哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇/>号码？
下面的比较与递归与迭代无关。 （它是
是一个常见的神话。）你（和其他人一样）正在比较一个指数的，b $ b O（1.6 ** n），算法与线性，O（ n），算法。
FWIW，但是完全有可能一个递归算法与
相同的渐近运行时是挂钟速度较慢，只是因为
所有额外的工作都涉及设置和拆除堆栈
帧并执行呼叫/返回指令。 （如果函数是
尾递归，你可以解决这个问题，虽然我不知道确切地知道如何实现CPython以及它是否优化了这种情况。）
Recursion is awesome for writing some functions, like searching trees
etc but wow how can it be THAT much slower for computing fibonacci-
numbers?
is the recursive definition counting fib 1 to fib x-1 for every x? is
that what lazy evaluation in functional languages avoids thus making
recursive versions much faster?
is recursive fibonacci in haskell as fast as an imperative solution in
a procedural language?
def fibr(nbr):
if nbr 1:
return fibr(nbr-1) + fibr(nbr-2)
if nbr == 1:
return 1
if nbr == 0:
return 0
def fibf(n):
sum=0
a=1
b=1
if n<=2: return 1
for i in range(3,n+1):
sum=a+b
a=b
b=sum
return sum
i found a version in Clojure that is superfast:
(def fib-seq
(concat
[0 1]
((fn rfib [a b]
(lazy-cons (+ a b) (rfib b (+ a b)))) 0 1)))
(defn fibx [x]
(last (take (+ x 1) fib-seq)))
(fibx 12000) is delivered instantly. is it using lazy evaluation?
Quoting slix <no**********@yahoo.se>:
Recursion is awesome for writing some functions, like searching trees
etc but wow how can it be THAT much slower for computing fibonacci-
numbers?The problem is not with ''recursion'' itself, but with the algorithm:
def fibr(nbr):
if nbr 1:
return fibr(nbr-1) + fibr(nbr-2)
if nbr == 1:
return 1
if nbr == 0:
return 0If you trace, say, fibr(5), you''ll find that your code needs to compute fibr(4)
and fibr(3), and to compute fibr(4), it needs to compute fibr(3) and fibr(2). As
you can see, fibr(3), and it whole subtree, is computed twice. That is enough to
make it an exponential algorithm, and thus, untractable. Luckily, the iterative
form is pretty readable and efficient. If you must insist on recursion (say,
perhaps the problem you are solving cannot be solved iteratively with ease), I''d
suggest you to take a look at ''dynamic programming'', or (easier but not
necesarily better), the ''memoize'' disgn pattern.
is the recursive definition counting fib 1 to fib x-1 for every x?Yes - that''s what the algorithm says. (Well, actually, the algorithm saysto
count more than once, hence the exponential behaviour). The memoize patter could
help in this case.
is
that what lazy evaluation in functional languages avoids thus making
recursive versions much faster?Not exactly... Functional languages are (or should be) optimized for recursion,
but if the algorithm you write is still exponential, it will still take along time.
is recursive fibonacci in haskell as fast as an imperative solution in
a procedural language?
[...]
i found a version in Clojure that is superfast:I''ve seen the haskell implementation (quite impressive). I don''t know Clojure
(is it a dialect of Lisp?), but that code seems similar to the haskell one. If
you look closely, there is no recursion on that code (no function calls).The
haskell code works by defining a list "fib" as "the list that starts with0,1,
and from there, each element is the sum of the element on ''fib'' plus the element
on ''tail fib''). The lazy evaluation there means that you can define a list based
on itself, but there is no recursive function call.
Cheers,
(I''m sleepy... I hope I made some sense)
--
Luis Zarrabeitia
Facultad de Matemática y Computación, UH
http://profesores.matcom.uh.cu/~kyrie
slix wrote:Recursion is awesome for writing some functions, like searching trees
etc but wow how can it be THAT much slower for computing fibonacci-
numbers?The comparison below has nothing to do with recursion versus iteration.
(It is a common myth.) You (as have others) are comparing an
exponential, O(1.6**n), algorithm with a linear, O(n), algorithm.
def fibr(nbr):
if nbr 1:
return fibr(nbr-1) + fibr(nbr-2)
if nbr == 1:
return 1
if nbr == 0:
return 0This is exponential due to calculating fib(n-2) twice, fib(n-3) thrice,
fib(n-4) 5 times, fir(n-5) 8 times, etc. (If you notice an interesting
pattern, you are probably correct!) (It returns None for n < 0.)
If rewritten as iteratively, with a stack, it is still exponential.
def fibf(n):
sum=0
a=1
b=1
if n<=2: return 1
for i in range(3,n+1):
sum=a+b
a=b
b=sum
return sumThis is a different, linear algorithm. fib(i), 0<=i<n, is calculated
just once. (It returns 1 for n < 0.) If rewritten (tail) recursively,
it is still linear.
In Python, an algorithm written with iteration is faster than the same
algorithm written with recursion because of the cost of function calls.
But the difference should be a multiplicative factor that is nearly
constant for different n. (I plan to do experiments to pin this down
better.) Consequently, algorithms that can easily be written
iteratively, especially using for loops, usually are in Python programs.
Terry Jan Reedy
On Sun, Jun 29, 2008 at 1:27 AM, Terry Reedy <tj*****@udel.eduwrote:>
slix wrote:>>
Recursion is awesome for writing some functions, like searching trees
etc but wow how can it be THAT much slower for computing fibonacci-
numbers?
The comparison below has nothing to do with recursion versus iteration. (It
is a common myth.) You (as have others) are comparing an exponential,
O(1.6**n), algorithm with a linear, O(n), algorithm.
FWIW, though, it''s entirely possible for a recursive algorithm with
the same asymptotic runtime to be wall-clock slower, just because of
all the extra work involved in setting up and tearing down stack
frames and executing call/return instructions. (If the function is
tail-recursive you can get around this, though I don''t know exactly
how CPython is implemented and whether it optimizes that case.)
这篇关于为什么递归这么慢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
