5

我有这个红宝石代码：

def get_sum n
    return 0 if n<1
  (n%3==0 || n%5==0) ? n+get_sum(n-1) : get_sum(n-1) #continue execution
end 

puts get_sum 999

似乎一直在为价值工作，直到999. 当我尝试9999时，它给了我这个：

stack level too deep (SystemStackError)

所以，我添加了这个：

RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false
}

但什么也没发生。

我的红宝石版本是：

ruby 1.9.3p392 (2013-02-22 revision 39386) [x86_64-darwin12.2.1]

我还增加了机器的堆栈大小ulimit -s 32768，我认为是 32MB？

我不认为这是我的代码的错，因为它适用于较小的数字，而且我认为这不是9999一个大数字。我有 8GB 的​​ RAM，我认为它已经足够了。有什么想法/帮助吗？

4

2 回答 2

9

您的方法不能利用尾调用优化 (TCO)，因为它不是tail-recursive，方法的最后一个表达式应该是对方法本身的调用，get_sum。所以没有错，只是你达到了递归限制。对于 Ruby 1.9.3，这个限制是：

def recursive(x)
  puts(x)
  recursive(x+1)
end

recursive(0)
...
8731

另一方面，这种方法是尾递归的：

def self.get_sum_tc(n, acc = 0)
  if n < 1
    acc
  else
    get_sum_tc(n - 1, acc + ((n % 3 == 0 || n % 5 == 0) ? n : 0))
  end
end

你的 Ruby 可能支持也可能不支持。在 Ruby 中，当您确定要达到的深度级别时，您可以使用递归，但循环遍历未知大小的集合绝对不是惯用的。您通常对此类任务有其他抽象，例如：

(1..9999).select { |x| x % 5 == 0 || x % 3 == 0 }.reduce(0, :+)
于 2013-04-03T13:18:49.693 回答
4

问题是，你有一个例程n+get_sum(n-1)，当 n 有公因数 3 或 5 时，Ruby 会继续执行这个例程。这不能通过尾递归进行优化。Ruby 必须保留当前帧以记住当前帧，n并且只有在get_sum(n-1)计算时 Ruby 才能返回并丢弃该帧。

通常，堆栈空间很昂贵。操作系统为每个进程保留大约 2M（可能更多）的堆栈空间。这可以很快消耗掉。对于您的代码，(9999/3 + 9999/5)递归调用消耗了所有堆栈空间。

如果要保持递归编程模式，则必须将方法调用的行为从递归（当前状态）更改为迭代。

def get_sum(n, sum = 0)
  return sum if n < 1
  if n % 3 == 0 || n % 5 == 0
    get_sum(n - 1, sum + n)
  else
    get_sum(n - 1, sum)
  end
end

然而，Ruby 的尾递归优化似乎并没有那么强大。对于上面的代码示例，有两个不同的get_sum()尾调用。Ruby 不会对此进行优化。您必须将这两个调用重写为一个。

此外，为了使这项工作与RubyVM您提供的调整一起工作，您必须在运行时加载方法定义。那是因为RubyVM调整发生在运行时。不能将方法定义直接放在同一个文件中，否则编译时会解析方法，优化不生效。

您可以在调整后将其放入get_sum单独的文件和require该库中RubyVM：

# file: test_lib.rb
def get_sum(n, sum = 0)
  if n < 1
    sum
  else
    get_sum(n - 1, sum + (n % 3 == 0 || n % 5 == 0 ? n : 0))
  end
end
# eof

# file: test.rb
RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false
}

require_relative 'test_lib'

puts get_sum(999999)

或者，用于eval在运行时评估 String 中的方法定义：

RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false
}

eval <<END
  def get_sum(n, sum = 0)
    if n < 1
      sum
    else
      get_sum(n - 1, sum + (n % 3 == 0 || n % 5 == 0 ? n : 0))
    end
  end
END

puts get_sum(990000)
于 2013-04-03T13:35:10.103 回答