末尾再帰をループにできないRustプログラムの例 - 簡潔なQ概要: 生存期間の関係で、ループでは書けないが末尾再帰では書けるアルゴリズムの例を挙げる。 単方向リンクリスト 次のような単純なリンクリストを考える。 struct List<T> { root: Option<Box<Node<T>>>, } struct Node<T> { value: T, next: Option<Box<Node<T>>>, } backの実装 単方向リンクリストの末尾要素の取得は O(n) である。これは次のように書くことができる。 impl<T> List<T> { fn back(&self) -> Option<&T> { let mut node = if let Some(ref b) = self.root { b.as_ref() } else { return None; }; while let Some(ref b) = node.next
