Ошибка: достигнут предел рекурсии при создании экземпляра `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
    }
}

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

Я обнаружил потенциально связанную проблему Rust , но она устарела, и я не могу хорошо понять процитированное сообщение в исходной проблеме.

• Что достигло предела рекурсии?
• Как обойти это, если я хочу инкапсулировать логику предикации в замыкание или что-то еще?

Алгоритм для проверки дерева двоичного поиска в этом коде не верен, но я все еще думаю, что оригинальный код должен компилировать .

Answer 1

@ Лукас Калбертодт приводит более простой пример, который я буду использовать в качестве основы для объяснения:

fn foo<F: Fn()>(x: bool, _: F) {
    if x {
        foo(false, || {}) // line 3
    }
}

fn main() {
    foo(true, || {}); // line 8
}

Важным моментом здесь является то, что каждое замыкание имеет уникальный тип, поэтому давайте создадим экземпляр этой программы:

• 1-е закрытие, в main, назовем тип main#8.
• 1-е создание foo, в main, foo<[main#8]>.
• 2-е закрытие, в foo, назовем тип {foo<[main#8]>}#3.
• 2-е создание foo, в foo, foo<[{foo<[main#8]>}#3]>.
• 3-е закрытие, в foo, назовем тип {foo<[{foo<[main#8]>}#3]>}#3.
• 3-й экземпляр foo, в foo, foo<[{foo<[{foo<[main#8]>}#3]>}#3]>.
• ...

Каждый новый экземпляр foo создает новый тип замыкания, каждый новый тип замыкания создает новый экземпляр foo, это рекурсия без базового случая: переполнение стека .

---

Вы можете решить проблему, НЕ создавая замыкание при рекурсивном вызове preorder_traverse:

• , либо используя стирание типа, хотя время выполнения большеhead,
• или просто с помощью отдельной внутренней функции для рекурсии, поскольку она не зависит от 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>).