Tail Call优化是否能解释这种性能差异
我看到了三种不同的方式来编写Fibonacci函数的递归forms：数学内联，数学内联结果缓存和一个使用尾递归。 我知道使用memoization在缓存答案后将O（N）算法转换为O（1）。 但我不明白尾调用优化如何帮助这么多。 我的印象是它可能会阻止一些副本或类似的东西。 它几乎和O（1）一样快。 Ruby做的是什么让这么快？
这是数学内联的慢速天真实现。 它显然是运行时间最慢的O（N）时间，然后在O（N ^ 2）时间内在显示器中循环。
puts Benchmark.measure { # Calculate the nth Fibonacci number, f(n). def fibo (n) if n <= 1 return n else value = fibo(n-1) + fibo(n-2) return value end end # Display the Fibonacci sequence. (1..40).each do |number| puts "fibo(#{number}) = #{fibo(number)}" end } Times Ruby 1.9.3：55.989000 0.000000 55.989000（55.990000）
Times JRuby 1.7.9：51.629000 0.000000 51.629000（51.629000）
来源（ http://rayhightower.com/blog/2014/04/12/recursion-and-memoization/?utm_source=rubyweekly ）
这是备忘录的版本，很明显为什么这对我来说很快。 完成数学后，任何后续请求都会在O（1）时间内运行，因此当它包含在循环中时，它仍会在最坏的情况下在O（N）时间内运行：
puts Benchmark.measure { # Fibonacci numbers WITH memoization. # Initialize the memoization array. @scratchpad = [] @max_fibo_size = 50 (1..@max_fibo_size).each do |i| @scratchpad[i] = :notcalculated end # Calculate the nth Fibonacci number, f(n). def fibo (n) if n > @max_fibo_size return "n must be #{@max_fibo_size} or less." elsif n <= 1 return n elsif @scratchpad[n] != :notcalculated return @scratchpad[n] else @scratchpad[n] = fibo(n-1) + fibo(n-2) return @scratchpad[n] end end # Display the Fibonacci sequence. (1..40).each { |number| puts "fibo(#{number}) = #{fibo(number)}" } }
Times Ruby 1.9.3：0.000000 0.000000 0.000000（0.025000）
次JRuby 1.7.9：0.027000 0.000000 0.027000（0.028000）
来源（ http://rayhightower.com/blog/2014/04/12/recursion-and-memoization/?utm_source=rubyweekly ）
这个版本的尾部调用递归版本可以立即运行：
puts Benchmark.measure { # Calculate the nth Fibonacci number, f(n). Using invariants def fibo_tr(n, acc1, acc2) if n == 0 0 elsif n < 2 acc2 else return fibo_tr(n - 1, acc2, acc2 + acc1) end end def fibo (n) fibo_tr(n, 0, 1) end # Display the Fibonacci sequence. (1..50).each do |number| puts "fibo(#{number}) = #{fibo(number)}" end }
Times Ruby 1.9.3：0.000000 0.000000 0.000000（0.021000）
次JRuby 1.7.9：0.041000 0.000000 0.041000（0.041000）
来源（ https://gist.github.com/mvidaurre/11006570 ）
尾递归不是这里的区别。 实际上，Ruby没有做任何事情来优化尾调用。
不同之处在于，naive算法在每次调用时递归调用自身两次，从而产生O（2 n ）性能，这意味着运行时随着N的增加呈指数增长。 尾部调用版本以线性时间运行。
TL; DR： 正如Chuck已经提到的，Ruby没有TCO。 但是，执行一次递归而不是两次递归会对您使用的堆栈数量以及完成的迭代次数产生很大影响。 有了这个答案，我只想指出，在某些时候，memoization版本比迭代版本更好。 注意：我不是ruby程序员。 它可能不是惯用的代码。
测试显示迭代方法如此之快，它可以从头开始生成1..50的fib，就像你的memoization版本在3以上的每个方法调用中重用计算一样快。
我认为1..50的速度非常快，以至于看迭代实际上是否更快是不可靠的。 我将memopization版本更改为：
# Initialize the memoization array. @scratchpad = [] # Calculate the nth Fibonacci number, f(n). def fibo (n) if n <= 1 return n end if @scratchpad[n].nil? @scratchpad[n] = fibo(n-1) + fibo(n-2) end return @scratchpad[n] end
然后我将循环更改为：
(1..5000).each { |number| fibo(number) # no need to time character output }
以下是我计算机上的结果：
Iteration: 6.260000 0.010000 6.270000 ( 6.273362) Memoization: 0.000000 0.000000 0.000000 ( 0.006943)
我用了：
ruby -v ruby 1.9.3p194 (2012-04-20 revision 35410) [x86_64-linux]
将memoization版本增加到1..50000仍然比迭代版本快得多。 原因是每次迭代都是从头开始，而memoization版本有一个更无效的算法但是memoization使它只为每个数字递归最多两次，因为我们有fib(n-1)和fib(n-2) in the array when calculating fib（n） fib(n-2) in the array when calculating 。
当然，最慢的是O(fib(n)) 。 迭代有O(n) 。 通过记忆，当计算fib(n-1)时， fib(n-2)是自由的，所以我们回到O(n)但是在你的测试中，你在下一个之前计算先前的斐波那契数，所以在实践中每个单独的迭代从1..x是O(1) 。 如果你从最高的数字开始，第一次迭代将是O(n)并且每一次迭代将是O(1) 。