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

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

（游乐场）：

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

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

我发现了一个可能相关的 Rust 问题，但它似乎已经过时了，我无法很好地理解原始问题中引用的消息。

• 什么达到了递归限制？
• 如果我想将预测逻辑封装在闭包或其他东西中，我该如何解决这个问题？

这段代码中验证二叉搜索树的算法不正确，但我仍然认为原始代码应该可以编译。

Answer 1

@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，让我们命名为 type {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>）。