rust 错误：示例化`func：：< [closure]>`时达到递归限制

jexiocij 于 2023-10-20 发布在其他

关注(0)|答案(2)|浏览(94)

我正在测试二叉搜索树是否有效：

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，但它似乎过时了，我不能很好地理解原始问题中引用的信息。

什么达到了递归极限？
如果我想把 predicate 逻辑封装在闭包或其他东西中，我该如何解决这个问题呢？

这段代码中验证二叉查找树的算法不正确，但我还是认为原代码应该编译。

rust

来源：https://stackoverflow.com/questions/54613966/error-reached-the-recursion-limit-while-instantiating-funcclosure

2条答案

按热度按时间

kgsdhlau1#

@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
    }
}

在夜间，您还可以创建 predicate 类型并为其实现Fn（LessThan<i32>和GreaterThan<i32>）。

赞(0）回复(0）举报 2023-10-20

vfh0ocws2#

一个我还没有看到讨论过的解决方法是：
定义你自己的trait，然后传入实现它的一个或另一个结构体。举例来说：

trait Comparison { fn compare(v: T, root: T) -> bool }

struct LessThan;
struct GreaterThan;

impl Comparison for LessThan {
  fn compare(v: T, root: T) -> bool { v < root }
}

impl Comparison for GreaterThan {
  fn compare(v: T, root: T) -> bool { v > root }
}

在您的情况下，这似乎有点多余，因为fn类型就可以了。然而，如果你确实想关闭某些东西，你可以向你的结构添加字段，然后在方法中使用这些字段。
这样，由于结构类型不依赖于（类型级别）示例化它们的位置，因此不会达到类型级别递归限制。

赞(0）回复(0）举报 2023-10-20

我来回答

rust 错误：示例化`func：：< [closure]>`时达到递归限制

2条答案

相关问题

热门标签

最新问答