Namaran

Code daily. Without assist.

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。

  1. -O2 を付けると GCC はこの depth をループに変換するので、直す前のコードでも 999999 が出ます。最適化なしのデバッグビルドでだけ落ちるのはこのためで、最適化に頼って動くコードは、ビルドの設定が変わると落ちます。