如何将尾递归重写为循环？

Question

我写了一个简单的前缀树变体：

struct Trie {
    data: Vec<Option<Trie>>
}

impl Trie {
    pub fn new() -> Trie {
        let mut data = Vec::with_capacity(26);
        for _ in 0..26 {
            data.push(None);
        }
        Trie { data: data }
    }

    pub fn add(&mut self, word: &str) {
        if word.len() != 0 {
            let idx = Trie::char_idx(word.char_at(0));
            let word_suffix = word.slice_from(1);
            if self.data[idx].is_none() {
                self.data[idx] = Some(Trie::new());
            } 
            self.data[idx].as_mut().unwrap().add(word_suffix)
        }
    }

    pub fn contain(&self, word: &str) -> bool {
        if word.len() == 0 {
            true
        } else {
            match self.data[Trie::char_idx(word.char_at(0))] {
                Some(ref next) => next.contain(word.slice_from(1)),
                None => false 
            }
        }
    }

    fn char_idx(chr: char) -> usize {
        (chr as u32 - 97) as usize
    }
}

除了 add 函数的递归性质外，它工作正常。现在，rust 没有尾调用优化，所以我需要将其重写为一个循环。这项任务应该是微不足道的，但如果没有借用检查员对我大喊大叫，我无法弄清楚如何做到这一点。

这是我天真的方法：

pub fn add(&mut self, word: &str) {
    let mut current = self; 
    for chr in word.chars() {
        let idx = Trie::char_idx(chr);
        if current.data[idx].is_none() {
            current.data[idx] = Some(Trie::new());
        }
        current = current.data[idx].as_mut().unwrap();
    }
}

我可以做什么？

Answer 1

我记得读过其他问同样概念性问题的问题，但我现在找不到。也许善良的灵魂会link他们在这里。

也就是说，编译：

pub fn add(&mut self, word: &str) {
    let mut current = self; 
    for chr in word.chars() {
        current = {
            let tmp = current;
            let idx = Trie::char_idx(chr);
            if tmp.data[idx].is_none() {
                tmp.data[idx] = Some(Trie::new());
            }
            tmp.data[idx].as_mut().unwrap()
        }
    }
}

我的总体想法是解决当前 borrow scopes are lexical 的问题。在 for 循环内部，我创建了一个新的词法作用域，然后将 current 重新借用为 tmp。我们在 tmp 上进行工作，最终返回一个引用，然后我们将其放回 current.

Answer 2

fold 似乎可以解决问题：

pub fn add(&mut self, word: &str) {
    word.chars().fold(
        self,
        |current, chr| {
            let idx = Trie::char_idx(chr);
            if current.data[idx].is_none() {
                current.data[idx] = Some(Trie::new());
            }

            current.data[idx].as_mut().unwrap()
        });
}

如何将尾递归重写为循环？

How to rewrite tail recursion as a cycle?

rust