我正在尝试测试二叉搜索树是否有效:
use std::{cell::RefCell, rc::Rc};
pub struct TreeNode {
val: i32,
left: Option<Rc<RefCell<TreeNode>>>,
right: Option<Rc<RefCell<TreeNode>>>,
}
pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
preorder_traverse(root.as_ref(), |_| true)
}
fn preorder_traverse<F: Fn(i32) -> bool>(root: Option<&Rc<RefCell<TreeNode>>>, predict: F) -> bool {
if let Some(node) = root {
let root_val = root.as_ref().unwrap().borrow().val;
if !predict(root_val) {
return false;
}
preorder_traverse(node.borrow().left.as_ref(), |v| v < root_val)
&& preorder_traverse(node.borrow().right.as_ref(), |v| v > root_val)
} else {
true
}
}
(Playground):
此代码触发以下错误消息,这对我来说似乎毫无意义:
error: reached the recursion limit while instantiating `preorder_traverse::<[closure@src/lib.rs:19:56: 19:72 root_val:&i32]>`
--> src/lib.rs:13:1
|
13 | / fn preorder_traverse<F: Fn(i32) -> bool>(root: Option<&Rc<RefCell<TreeNode>>>, predict: F) -> bool {
14 | | if let Some(node) = root {
15 | | let root_val = root.as_ref().unwrap().borrow().val;
16 | | if !predict(root_val) {
... |
23 | | }
24 | | }
| |_^
我找到了 a potentially related Rust issue , 但它似乎过时了,我无法很好地理解原始问题中引用的消息。
- 什么达到了递归限制?
- 如果我想将谓词逻辑封装在闭包或其他东西中,我该如何解决这个问题?
此代码中验证二叉搜索树的算法不正确,但我仍然认为原始代码应该编译。
最佳答案
@Lukas Kalbertodt 提供了一个更简单的示例,我将以此作为解释的基础:
fn foo<F: Fn()>(x: bool, _: F) {
if x {
foo(false, || {}) // line 3
}
}
fn main() {
foo(true, || {}); // line 8
}
这里的重点是每个闭包都有一个唯一的类型,所以让我们实例化这个程序:
- 第一次关闭,在
main
,让我们将类型命名为main#8
. foo
的第一次实例化, 在main
,foo<[main#8]>
.- 第二次关闭,在
foo
,让我们将类型命名为{foo<[main#8]>}#3
. foo
的第二次实例化, 在foo
,foo<[{foo<[main#8]>}#3]>
.- 第三次关闭,在
foo
, 让我们命名类型{foo<[{foo<[main#8]>}#3]>}#3
. foo
的第三次实例化, 在foo
,foo<[{foo<[{foo<[main#8]>}#3]>}#3]>
.- ...
foo
的每个新实例创建一个新的闭包类型,每个新的闭包类型都会创建一个新的实例 foo
,这是一个没有基本情况的递归:堆栈溢出。
您可以通过在递归调用 preorder_traverse
时不创建闭包来解决问题。 :
- 要么使用类型删除,尽管有运行时开销,
- 或者简单地使用一个单独的递归内部函数,因为它独立于
F
.
例子:
fn preorder_traverse_impl(
root: Option<&Rc<RefCell<TreeNode>>>,
parent_value: i32,
predict: fn(i32, i32) -> bool
)
-> bool
{
if let Some(node) = root {
let root_val = root.as_ref().unwrap().borrow().val;
if !predict(root_val, parent_value) {
return false;
}
preorder_traverse_impl(node.borrow().left.as_ref(), root_val, lessThan)
&& preorder_traverse_impl(node.borrow().right.as_ref(), root_val, greaterThan)
} else {
true
}
}
fn preorder_traverse<F: Fn(i32) -> bool>(root: Option<&Rc<RefCell<TreeNode>>>, predict: F) -> bool {
if let Some(node) = root {
let root_val = root.as_ref().unwrap().borrow().val;
if !predict(root_val) {
return false;
}
preorder_traverse_impl(node.borrow().left.as_ref(), root_val, lessThan)
&& preorder_traverse_impl(node.borrow().right.as_ref(), root_val, greaterThan)
} else {
true
}
}
在夜间,您还可以创建谓词类型并实现 Fn
为此( LessThan<i32>
和 GreaterThan<i32>
)。
关于rust - 错误 : reached the recursion limit while instantiating `func::<[closure]>` ,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54613966/