错误：在实例`FUNC达到递归限制::`

Question

我想测试一个二叉搜索树是有效的：

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

（Qazxswpoi）：

此代码触发以下错误消息，这似乎无感对我说：

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 | | }
   | |_^

，但似乎已经过时，我无法理解在原来的问题引述消息很好。

• 什么击中了递归限制？
• 我怎样才能解决这个，如果我想封装在封闭或别的东西的预测逻辑是什么？

该算法来验证这个代码二叉搜索树是不正确的，但我仍然认为原来的代码应该编译。

Answer 1

@Lukas Kalbertodt提供了一个简单的例子，我将作为解释的基础使用方法：

a potentially related Rust issue

这里最重要的一点是，每封都有一个唯一的类型，让我们实例化这个程序：

• 1日关闭，在

  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>）。