java - 无法理解何时必须将 return 语句与递归关联使用
问题描述
我正在复习递归的概念并使用二叉树。我不明白使用带有递归调用的 return 语句的实例与其他不使用 return 的实例之间的区别。我将给出说明我的问题的代码。
这是一个检查 BST 中是否存在值的函数:
public boolean containsNodeRecursive(Node current, int value) {
if (current == null) {
return false;
}
if (value == current.data) {
return true;
}
//HERE, THE RECURSIVE CALL IS PRECEDED BY A RETURN STATEMENT
return value < current.data
? containsNodeRecursive(current.left, value)
: containsNodeRecursive(current.right, value);
}
}
这是一个将数据插入 BST 的函数:
public Node insert(Node current, int data) {
if (current == null) {
return createNode(data);
} else if (data < current.data) {
//RECURSIVE CALL HERE WITHOUT USE OF A RETURN STATEMENT
current.left = insert(current.left, data);
} else if (data > current.data) {
current.right = insert(current.right, data);
}
return current;
}
我想我的问题可以归结为:“我们什么时候应该返回递归调用,什么时候不应该?”</p>
解决方案
存在两种类型的函数,因此我们需要遵循两个单独的规则。
采用您提供的第一个功能:
public boolean containsNodeRecursive(Node current, int value) {
if (current == null) {
return false;
}
if (value == current.data) {
return true;
}
//HERE, THE RECURSIVE CALL IS PRECEDED BY A RETURN STATEMENT
return value < current.data
? containsNodeRecursive(current.left, value)
: containsNodeRecursive(current.right, value);
}
}
此函数旨在查找单个目标值并将其返回。在这种情况下,当我们想要返回一个我们知道将由被测试节点的单个子节点提供的值时,我们会返回一个递归调用。
但是,以插入为例:
public Node insert(Node current, int data) {
if (current == null) {
return createNode(data);
} else if (data < current.data) {
//RECURSIVE CALL HERE WITHOUT USE OF A RETURN STATEMENT
current.left = insert(current.left, data);
} else if (data > current.data) {
current.right = insert(current.right, data);
}
return current;
}
此代码旨在完成不同类型的任务。此递归函数旨在修改现有树,而不是寻求单个目标值。在这种情况下,我们只返回我们想要对现有树(或重复值)进行的修改。