Namaran

Code daily. Without assist.

2026-10-07

collatz.rs

use std::cell::RefCell;
use std::collections::HashMap;

fn steps(memo: &RefCell<HashMap<u64, u32>>, n: u64) -> u32 {
    match memo.borrow().get(&n) {
        Some(&s) => s,
        None => {
            let next = if n.is_multiple_of(2) { n / 2 } else { 3 * n + 1 };
            let s = steps(memo, next) + 1;
            memo.borrow_mut().insert(n, s);
            s
        }
    }
}

fn main() {
    let memo = RefCell::new(HashMap::from([(1, 0)]));
    println!("{}", steps(&memo, 6));
}

steps は、n が偶数なら2で割り、奇数なら3倍して1を足す、という操作を何回繰り返すと1になるかを、求めた回数を memo に覚えながら再帰で求めるつもりの関数です。main は n = 6 について求めます。引数も標準入力も使いません。いまは何も出力されず、RefCell already borrowed というメッセージで panic します。本来は 8 が出るはずです。

Answer

Wrong

match memo.borrow().get(&n) {
    Some(&s) => s,
    None => {
        let next = if n.is_multiple_of(2) { n / 2 } else { 3 * n + 1 };
        let s = steps(memo, next) + 1;
        memo.borrow_mut().insert(n, s);

memo.borrow() が返す Ref は、ドロップされるまで RefCell を共有で借りたままにします。この Ref は match の条件式の中で作った一時値で、条件式の一時値は match 全体が終わるまで生きます。そのため None の腕で再帰呼び出ししている間も、呼び出し元の steps は memo を借りたままです。

steps(6) から steps(3)、steps(10) と降りていく間は、共有の借用どうしは重なってよいので何も起きません。steps(1) がメモにある 0 を返し、steps(2) に戻って borrow_mut() を呼んだところで、steps(2) 自身とその呼び出し元すべてがまだ借りているので panic します。

Right

let cached = memo.borrow().get(&n).copied();
match cached {
    Some(s) => s,

let 文の中の一時値は、その文の終わりでドロップされます。copied() で Option<&u32> を Option<u32> にしておけば、cached はメモへの参照を持たないので、Ref は次の行に進む前に返されます。再帰呼び出しの間はだれも memo を借りていないので、borrow_mut() が通り、8 が出ます。

match memo.borrow().get(&n).copied() のように条件式の中で copied() を付けるだけでは直りません。値は複製されても、Ref そのものが条件式の一時値として match の終わりまで残るからです1。

  1. memo が &mut HashMap なら、元の match の形のままでもコンパイルが通り、正しく動きます。コンパイラの借用検査は参照が最後に使われた所で借用を終わらせますが、RefCell の借用は Ref がドロップされるまで終わらないからです。