为什么我会通过递归获得“堆栈级别太深”?
我有这个ruby代码:
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版本是:
ruby 1.9.3p392 (2013-02-22 revision 39386) [x86_64-darwin12.2.1]
我还增加了机器的堆栈大小ulimit -s 32768
,我认为是32MB?
我不认为这是我的代码的错,因为它适用于较小的数字,我不认为9999
是一个大数字。 我有8GB的RAM,我认为这已经足够了。 任何想法/帮助?
您的方法无法利用尾调用优化(TCO),因为它不是尾递归的 ,方法的最后一个表达式应该是对方法本身的调用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, :+)
问题是,你有一个例程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
放在一个单独的文件中,并在RubyVM
调整后require
该lib:
# 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 <