为什么我不能将这个尾递归函数转换为 Rust 中的迭代函数？

Question

我正在编写一个从单链表中删除最后一个节点的函数：

#[derive(PartialEq, Eq, Debug)]
struct Node<T> {
    value: T,
    next: Option<Box<Self>>,
}

这是我的递归版本：

fn remove_last_node_recursive<T>(node_ref: &mut Option<Box<Node<T>>>) {
    let next_ref = &mut node_ref.as_mut().unwrap().next;

    if next_ref.is_some() {
        remove_last_node_recursive(next_ref);
    } else {
        *node_ref = None;
    }
}

递归版本工作正常，但我想写一个像下面这样的迭代版本：

fn remove_last_node_iterative<T>(mut node_ref: &mut Option<Box<Node<T>>>) {
    loop {
        let next_ref = &mut node_ref.as_mut().unwrap().next;

        if next_ref.is_some() {
            node_ref = next_ref;
        } else {
            break;
        }
    }

    *node_ref = None; // This line causes lifetime error.
}

我认为我的递归版本是尾递归的，所以我应该可以将其转换为迭代版本，但正如评论所说，由于生命周期错误，评论代码无法编译：

error[E0506]: cannot assign to `*node_ref` because it is borrowed
  --> src/main.rs:28:5
   |
17 | fn remove_last_node_iterative<T>(mut node_ref: &mut Option<Box<Node<T>>>) {
   |                                                - let's call the lifetime of this reference `'1`
18 |     loop {
19 |         let next_ref = &mut node_ref.as_mut().unwrap().next;
   |                             -----------------
   |                             |
   |                             borrow of `*node_ref` occurs here
   |                             argument requires that `*node_ref` is borrowed for `'1`
...
28 |     *node_ref = None; // This line causes lifetime error.
   |     ^^^^^^^^^ assignment to borrowed `*node_ref` occurs here

您可以测试 the rust playground 中的代码。

我做错了什么，正确的做法是什么？

Answer 1

您的问题是可变引用的关键路径。

由于错误消息已经提到您可变地借用 node_ref 值并分配给 node_ref 变量，因此它会进入函数范围 - 与您的 None 分配相同 - 因为 break 可能发生。您可以检查一个没有可变性的下一个值，并在您的条件的内部范围内借用可变的，这样它就可以工作：

fn remove_last_node_iterative<T>(mut node_ref: &mut Option<Box<Node<T>>>) {
    while node_ref.as_ref().unwrap().next.is_some() {
        node_ref = &mut node_ref.as_mut().unwrap().next;
    }
    *node_ref = None;
}

为什么我不能将这个尾递归函数转换为 Rust 中的迭代函数？

Why can’t I convert this tail recursive function into an iterative one in Rust?

lifetime

rust

singly-linked-list