2026-10-02
depth.cpp
#include <iostream>
#include <vector>
int depth(const std::vector<int>& parent, int i) {
if (parent[i] == -1)
return 0;
return 1 + depth(parent, parent[i]);
}
int main() {
std::vector<int> parent(1'000'000);
for (int i = 0; i < 1'000'000; ++i)
parent[i] = i - 1;
std::cout << depth(parent, 999'999) << '\n';
}
parent[i] は節点 i の親で、根の親は -1 です。depth は、節点 i から根までにたどる辺の数を返すつもりの関数です。main は100万個の節点を1列につないだ木を作り、末端の節点の深さを出力します。引数も標準入力も使いません。本来は 999999 と出力されるはずが、最適化を付けずにビルドすると、いまは何も出力せずに Segmentation fault で落ちます。
Answer
Wrong
int depth(const std::vector<int>& parent, int i) {
if (parent[i] == -1)
return 0;
return 1 + depth(parent, parent[i]);
}
末端の節点 999999 から根の 0 までたどるあいだに、depth は自分自身を999999回呼びます。1 + depth(...) は呼んだ depth が戻ってから 1 を足すので、足し算が済むまで呼び出し元のフレームは残ります。フレームが100万段積み上がってスタックの上限を超え、落ちます。
Right
int depth(const std::vector<int>& parent, int i) {
int d = 0;
for (; parent[i] != -1; i = parent[i])
++d;
return d;
}
親へ1段進むたびに d を1増やすループにすれば、何段たどっても使うフレームは depth の1つだけです。
足し算を引数に移して return depth(parent, parent[i], d + 1); のような末尾呼び出しにする手もありますが、C++ の規格は、その呼び出しをジャンプに置き換える最適化を保証していません。入力しだいで深さがいくらでも大きくなる再帰は、ループに書き直すのが確実です1。
-O2を付けると GCC はこのdepthをループに変換するので、直す前のコードでも999999が出ます。最適化なしのデバッグビルドでだけ落ちるのはこのためで、最適化に頼って動くコードは、ビルドの設定が変わると落ちます。