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