自分で書いたプログラムが固まって、いつまで待っても返ってこない——その原因が無限ループだった、という経験はないでしょうか。やっかいなのは、次へ、次へ とデータをたどっていく類の処理が、輪にハマったときです。

たとえば、連結リストをたどるコードを書いたとします。本来は末尾（null）で終わるはずが、データが壊れて途中のノードが前のノードを指していたら、たどる処理は終点にたどり着けず、同じ環をぐるぐる回り続けます。連結リストに限らず、「ある値から次の値を計算して進む」「状態 A から次の状態へ遷移する」——こうした「次をたどる」ロジックを自分で書くとき、どこかで輪に入り込んでいないかは、コードを眺めただけでは分かりません。

この記事で扱うのは、そういう自分のコードに「隠れた輪」が無いかを、たどりながら確かめる方法です。具体的には、連結リストが壊れて循環していないかのチェック、配列の重複探し（配列を「次をたどる写像」とみなします）、あるいは自分の反復ロジックがループに落ちないかをテストで確かめたいとき——どれも同じ道具ひとつで済みます。

素朴にやるなら、「訪れた場所を全部メモ（集合）しておいて、すでに来たことのある場所に戻ったら輪あり」とすればいい。正しく動きますが、訪れた数だけメモリ（$O(n)$）が要ります。

この記事の主役は、メモを一切持たず——変数2つ、追加メモリ $O(1)$——で輪を見つける、フロイドの循環検出（カメとウサギ）です。最後に、ブラウザだけで動くビジュアライザで実際に動かし、前回の玉突き方式 の無限ループにも当てはめてみます。

まず、輪のある列は「ρ（ロー）の形」になる

「現在の場所 → 次の場所」が毎回決まっている列をたどると、形は必ずρ（ギリシャ文字のロー）のようになります。輪に入るまでの一本道（しっぽ）と、ぐるぐる回る輪です。

「次へ」を辿る列はρの形になる。一本道＋輪で、輪の最後は入口へ戻る

輪の最後のノードの「次」は、輪の入口に戻ります。だから一度入ると二度と出られず、回り続ける。やりたいのは「輪があるか」、できれば「輪の入口はどこか」を知ることです。

カメとウサギ：ポインタ2つで追いつく

フロイドの方法は、拍子抜けするほど単純です。同じスタートから、速さの違う2つのポインタを走らせます。

  • 🐢 カメ：1歩ずつ進む
  • 🐇 ウサギ：2歩ずつ進む

第1幕。 輪が無ければ、ウサギが先に終点（行き止まり）へ着きます。輪があれば、ウサギは輪の中をぐるぐる回り、いつか必ずカメに追いつきます。なぜなら、2匹が輪に入ったあとは、ウサギはカメに毎ステップ1つずつ近づくから。差が1ずつ縮むので、飛び越してすれ違うことはなく、必ずピッタリ一致します（差が1ずつしか減らない以上、輪の長さが偶数でも奇数でも必ず 0 を通ります）。一致したら、輪がある証拠です。

第2幕。 ここがエレガントなところ。出会った地点にカメを残し、もう1つのポインタを起点（スタート）に戻して、今度は両方とも1歩ずつ進めます。すると、ちょうど輪の入口で再会します。これで輪の始まりまで分かります。

function detectCycle(start, next){
  let slow = start, fast = start;
  // 第1幕：出会うまで（出会わずに終点へ着けば輪は無い）
  do {
    slow = next(slow);                          // 1歩
    fast = next(fast); if(fast === null) return null; // 2歩（1歩ごとに終点を確認）
    fast = next(fast); if(fast === null) return null;
  } while(slow !== fast);

  // 第2幕：起点と出会った地点から1歩ずつ → 入口で再会
  let p = start;
  while(p !== slow){ p = next(p); slow = next(slow); }
  return p;                        // 輪の入口
}

使っているのは slow と fast（と p）という変数だけ。列がどれだけ長くても、メモリは増えません。これが $O(1)$ の意味です。

なぜ第2幕で入口に揃うのか

一本道の長さを $\mu$、輪の長さを $\lambda$ とします。第1幕でカメが進んだ距離を $d$ とすると、ウサギはその倍の $2d$ 進んで同じ場所にいるので、その差 $d$ は輪の長さ $\lambda$ の倍数です。つまりカメは「$\lambda$ の倍数ぶん」だけ余計に回った場所にいる。ここから、起点と出会い地点をそれぞれ1歩ずつ進めると、ちょうど $\mu$ 歩で両者が入口に重なります。証明は1行で、紙とペンでも追えます。

触ってみる

実際に動かして確かめられるようにしました。下のビジュアライザを触ってみてください。

  • 上の方式を「カメとウサギ／訪問済みメモ」で切り替えると、メモリを使う/使わないの差がそのまま見えます。訪問済みメモ方式は通ったノードがどんどん溜まりますが、カメとウサギは🐢🐇の2匹だけです。
  • 「一本道の長さ」「輪の長さ」をスライダーで変えて、輪がどんな形でも必ず追いつき、入口で揃うことを確かめてみてください。
  • 「最初から再生」で第1幕（追いつく）→第2幕（入口で再会）を1ステップずつ追えます。

うまく表示されないときは、ビジュアライザを別タブで開く 。

本番ではどう使うのか

カメとウサギは、テスト用というより本番のロジックに直接組み込んで使うのが本筋です。使い方は大きく2通りあります。

① 「輪を見つけること」自体が目的の処理に、アルゴリズムとして使う。

いちばん有名なのが配列の重複探しです。「1〜n の値が入った、長さ n+1 の配列。重複が必ず1つある。それを、配列を書き換えず・追加メモリ $O(1)$ で見つけたい」という問題を考えます。配列を i → arr[i] という「次をたどる写像」とみなすと、重複した値がちょうど輪の入口になります。あとはカメとウサギで入口を探すだけ。

// arr: 1〜n の値が入った長さ n+1 の配列（重複が1つある）
// arr を「i → arr[i]」という写像とみなして輪の入口を探す
function findDuplicate(arr){
  let slow = arr[0], fast = arr[0];
  do {                          // 第1幕：出会うまで
    slow = arr[slow];
    fast = arr[arr[fast]];
  } while(slow !== fast);
  slow = arr[0];                // 第2幕：起点と出会い地点から1歩ずつ
  while(slow !== fast){ slow = arr[slow]; fast = arr[fast]; }
  return slow;                  // 輪の入口 ＝ 重複した値
}

ソートも追加の配列も要らず、$O(n)$ 時間・$O(1)$ メモリで重複が求まります。同じ原理は、巨大な数を素因数分解するPollard’s ρ（ロー）法や、乱数生成器が同じ並びを繰り返し始める周期の検出（Knuth がフロイドの方法を紹介した、まさにその用途）でも本番の心臓部として使われています。

② 巡回しうる処理の「安全弁」として組み込む。

参照やポインタを 次へ とたどる処理——シンボリックリンクの解決、親要素を遡る、依存関係をたどる——に忍ばせておき、壊れたデータで輪に入ったら、固まる代わりに即エラーで抜けるようにします。

ただし正直に言うと、「ただ永遠に固まらなければいい」だけなら、フロイドより単純な手で足りることも多いです。「N 回たどっても終わらなければ打ち切る」というステップ数の上限や、訪問済みメモ（$O(n)$）で済むなら、その方が読みやすい。カメとウサギが本当に効くのは、①メモリを $O(1)$ に抑えたい、かつ ②輪の存在だけでなく入口（＝重複した値や周期の先頭）まで正確に突き止めたい——この両方が要るときです。

コラム：玉突き方式の無限ループに当てはめる

前回の玉突き方式（循環置換） を思い出してください。あれは j = perm[j]（次の位置へ飛ぶ）を繰り返して鎖をたどる処理でした。これはまさに「同じ写像をたどる列」——この記事の next がちょうど perm なんです。

玉突きでは、対応表が壊れていない（全単射である）ことを実行前に検査していました。もしこの検査を怠って perm に重複や抜けがあると、j = perm[j] をたどっても出発点に戻ってこない輪にハマり、「出発点に戻るまで」という素朴な停止条件だと無限ループします。玉突き記事ではこれを visited（訪問済み集合）で防いでいましたが、それは $O(n)$ のメモリ。

ここをカメとウサギに置き換えれば、訪問済み集合を持たずに $O(1)$ メモリで「輪にハマった」を検出できます。「実体ではなく目印（ポインタ）を動かす」という、このシリーズ共通の発想がここでも効くわけです。

ここを勘違いしやすい（私も最初ハマりました）

「じゃあ、既存のどんなプログラムにもカメとウサギを注入すれば、無限ループに落ちるか検証できるのでは？」——これはできません。とても自然な発想なのですが、ここに落とし穴があります。

カメとウサギは「万能の無限ループ検出器」ではありません。「任意のプログラムが停止するか否か」を判定する万能の方法は、原理的に作れないことが証明されています（停止性問題）。

カメとウサギが効くのは、ループが次の特定の形のときだけです。

  • 「現在の状態 → 次の状態」が、毎回同じ関数 next で決まる（決定的・外部入力なし）。
  • 状態を複製して同値比較できる（連結リストのノード、整数、置換のインデックスなど）。

連結リストの node.next、整数列の (a*x+c) % n、玉突きの perm[j] は、どれもこの形なので注入できます。逆に、ファイルやネットワークから毎回違う入力を読む・状態が無限に増える、といった普通のアプリには当てはまりません。「next という決定的な1関数に話を絞れたときだけ効く道具」と覚えておくと、混乱しません。

シリーズの仲間

このシリーズは「サイクル（輪）」と「目印を動かす」という発想で繋がっています。

今回のカメとウサギは、その「サイクル」を見つける側の道具でした。応用も派手で、配列の重複要素探し（配列を写像とみなす）や Pollard’s ρ（ロー）素因数分解にそのまま効きます。

まとめ

  • 「次へ」を辿る列の輪は、訪問済みメモ（$O(n)$）でも見つかるが、メモリを食う。
  • フロイドの循環検出（カメとウサギ）は、1歩のカメと2歩のウサギを走らせるだけ。第1幕で必ず追いつき（＝輪あり）、第2幕で入口を特定。追加メモリは変数2つ＝$O(1)$。
  • 玉突き方式の j = perm[j] はまさにこの適用例。$visited$（$O(n)$）を $O(1)$ に置き換えられる。
  • ただし万能の無限ループ検出器ではない。効くのは「決定的な next を繰り返す列」に限る（一般の停止判定は停止性問題で不可能）。

参考文献

  • フロイドの循環検出：実は Robert W. Floyd 本人による原典論文は知られておらず、Donald Knuth が著書『The Art of Computer Programming, Vol. 2: Seminumerical Algorithms』(1969) の中で出典なしにフロイドへ帰属させたのが初出とされます（誰の発明か特定できない「フォークロア」とも言われます）。経緯は Wikipedia: Cycle detection に詳しいです。
  • 停止性問題：A. M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proc. London Math. Soc., ser. 2, vol. 42 (1936–37), pp. 230–265. DOI: 10.1112/plms/s2-42.1.230 。概説は Wikipedia: 停止性問題 を参照。

理屈だけだとピンと来にくいので、ぜひ上のビジュアライザで一本道や輪の長さを変えながら、🐢と🐇が必ず出会い、入口でぴたりと揃う様子を眺めてみてください。