我的代码在树中搜索目标，但这是递归的吗?

Question

我正在尝试搜索一个简单的树来查找目标值。我的指示是使用递归。我知道递归意味着(部分(该方法是从自身内部调用的。从这个意义上说，以下代码成功。但是，我也理解(我认为(递归需要设置一个查询，该查询在达到基本情况之前无法解决，此时答案将在链中传递回，并且可以解决每个未解决的查询。我的代码并没有真正做到这一点(我认为(。我需要更高的力量来向我(希望还有其他人(指明道路。

class Tree
attr_accessor :payload, :children
def initialize(payload, children)
@payload = payload
@children = children
end
def self.test (node, target)
if node.payload == target
print "Bingo!"
else
print node.payload
end
node.children.each do |child|
Tree.test(child, target)
end
end
end

# The "Leafs" of a tree, elements that have no children
deep_fifth_node = Tree.new(5, [])
eleventh_node = Tree.new(11, [])
fourth_node   = Tree.new(4, [])
# The "Branches" of the tree
ninth_node = Tree.new(9, [fourth_node])
sixth_node = Tree.new(6, [deep_fifth_node, eleventh_node])
seventh_node = Tree.new(7, [sixth_node])
shallow_fifth_node = Tree.new(5, [ninth_node])
# The "Trunk" of the tree
trunk   = Tree.new(2, [seventh_node, shallow_fifth_node])
Tree.test(trunk, 5)

Answer 1

假设你的函数调用自己(而你的函数似乎调用自己(，你正在使用递归。有关递归的良好讨论，请参阅 https://softwareengineering.stackexchange.com/questions/25052/in-plain-english-what-is-recursion。

为了防止无限递归，你需要一个基本情况，确保你最终完全解开所有内容，而不是简单地永远继续调用你的函数，而且很多时候，当你完全完成正在运行的任何计算时，但这并不一定意味着在你到达基本情况之前你找不到你要找的东西(在搜索的情况下(。

Answer 2

是的，你的函数正在使用递归：它调用自己。

以下是针对您的方法的建议：

def find_nodes_with_payload?(target, result = [])
if payload == target
result << self
end
children.each do |child|
child.find_nodes_with_payload?(target, result)
end
accu
end

该方法将收集包含特定目标值的(子(树中的所有节点。能解决你的问题吗？

我通过以下方式修改了您的原始代码：

• 使其成为实例方法并删除了"node"参数
• 恕我直言，将其从"测试"重命名为更具描述性的内容
• 添加了一个数组，用于收集包含有效负载的所有节点
• 将逻辑更改为：如果条件不匹配，则不执行任何操作，但再次递归调用所有子项的方法

Answer 3

你可以让它变得简单。

def search(tree, target)
trav = ->(node) { node.val == target ? puts("Bingo") : node.leaves.each(&trav) }
trav[tree]
end

树的创建也可以简化。

Node = Struct.new(:val, :leaves)
add = ->(tree) { tree ? tree.map {|k,v| Node.new(k, add[v])} : [] }

因此，我们可以递归创建树并找到价值。

sample_tree = {2 => {7 => {6 => {4=>{}, 11=>{}}}, 5=> {9 => {}, 4=>{}}}}
tree = add[sample_tree]
search(tree.first, 5)