Namaran

Code daily. Without assist.

2026-10-31

find_root.rs

fn root(parent: &[usize], i: usize) -> usize {
    if parent[i] == i {
        i
    } else {
        root(parent, parent[i])
    }
}

fn main() {
    let parent: Vec<usize> = (0..1_000_000).map(|i: usize| i.saturating_sub(1)).collect();
    println!("{}", root(&parent, 999_999));
}

parent[i] は要素 i の親で、自分自身を親に持つ要素を根と呼びます。root は i から親をたどって根を返すつもりの関数です。main は、999999 の親が 999998、999998 の親が 999997、と100万個が一列に並び、0 が根になる表を作って root(&parent, 999_999) を呼びます。本来は 0 と出力されるはずが、いまは最適化なしでビルドして実行すると、何も出力せずに、スタックを使い切ったというメッセージを出して異常終了します。

Answer

Wrong

fn root(parent: &[usize], i: usize) -> usize {
    if parent[i] == i {
        i
    } else {
        root(parent, parent[i])
    }
}

root は親を1つたどるたびに自分を呼び、呼び出しは根に着くまで戻りません。999_999 から 0 までたどると呼び出しは100万段になり、1段ごとに積まれるスタックフレームがメインスレッドのスタックに収まりきらなくなります。

root(parent, parent[i]) は関数の最後の式で、呼び出したあとにする仕事は残っていません。それでも Rust は、こうした末尾の位置にある呼び出しで今のスタックフレームを再利用するとは保証していません1。最適化を有効にすると LLVM がループに書き換えて 0 が出ることもありますが、それは最適化の結果で、言語の規則ではありません。

Right

fn root(parent: &[usize], mut i: usize) -> usize {
    while parent[i] != i {
        i = parent[i];
    }
    i
}

親をたどる再帰を、i を書き換えるループにしました。呼び出しはなくなり、使うスタックは表の長さにかかわらず root の1段分だけなので、最適化なしでも 0 が出力されます。

  1. Rust は become を予約語にしています。become f(x) と書いた呼び出しでスタックフレームの再利用を保証させる機能が検討されていますが、安定版にはまだ入っていません。