Tag: recursion

Ruby递归DFS方法

我在深度优先搜索算法实现的递归方法上遇到了一些麻烦。 这是二叉树照片： 该方法适用于树的右侧（55,89,144），但是当它到达左侧时返回nil，即使它放置“是”。 那么，代码有什么问题？ 该节点是Node类的一个实例，它具有值（整数）以及指向左右子节点（Node类的其他实例）的链接，如果它没有来自该节点的子节点则为nil。 这是方法代码： def depth_first_search(node, target) if node.value == target puts “yes” return node end depth_first_search(node.child_left, target) if node.child_left depth_first_search(node.child_right, target) if node.child_right end

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 […]

在递归例程中是否存在“堆栈级太深”错误的解决方法？

Ruby中的递归函数中是否存在Stack Overflow错误的解决方法？ 比方说，我有这个块： def countUpTo(current, final) puts current return nil if current == final countUpTo(current+1, final) end 如果我调用countUpTo(1, 10000) ，我会收到一个错误： stack level too deep (SystemStackError) 。 它似乎在8187处突破。是否有一些函数我可以调用告诉Ruby忽略堆栈的大小，或者增加最大堆栈大小的方法？