是尾巴呼叫优化所有解释此性能差异

Question

我看到了三种不同的方式来编写斐波那契函数的递归形式：数学内联，数学内联结果缓存和一个使用尾递归。我知道使用memoization将O（N）算法转换为O（1），缓存后的答案。但我无法理解tail call优化如何能够提供如此大的帮助。我的印象是它可能会阻止一些副本或类似的东西。它几乎和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 
} 

时报红宝石1.9.3：55.989000 0.000000 55.989000（55.990000）
时报的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）

这里是一个memoizes答案版本，这很明显为什么这对我来说很快。一旦它已经做任何以下请求运行在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)}" 
    } 
} 

时报红宝石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 
} 

时报红宝石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）

Answer 1

尾递归是不是这里的区别。实际上，Ruby并没有做任何事情来优化尾部调用。

不同之处在于，天真算法在每次调用时递归调用两次，给出了O（2 ⁿ）的性能，这意味着随着N增加，运行时间呈指数增长。尾调用版本以线性时间运行。

Answer 2

TL; DR：正如Chuck已经提到的，Ruby没有TCO。但是，执行一次递归而不是两次会对您使用多少堆栈以及完成多少次迭代产生重大影响。有了这个答案，我只想指出，在某些时候，memoization版本比迭代版本更好。注意：我不是一个红宝石程序员。它可能不是惯用代码。

试验表明迭代的方法是如此之快就可以从头开始一样快，产生的1..50 FIB为您的记忆化版本重用计算在每一个方法调用上述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] 

增加memoiza版本到1..50000仍然比迭代版本快得多。原因是迭代每次都从头开始，而memoization版本有一个更无效的算法，但memoization使它只能为每个数字递归最多两次，因为我们有fib(n-1)和fib(n-2) in the array when calculating fib（n）`。

当然最慢的有O(fib(n))。迭代有O(n)。随着记忆的fib(n-2)是免费的，当计算fib(n-1)，所以我们回到O(n)，但在你的测试中，你计算之前的斐波那契数字，因此在实践中，从1..x每个单独的迭代是O(1)。如果你从最高的数字开始，第一次迭代将是O(n)，并且接下来的每一次将是O(1)。