【C++】再帰関数への引数の渡し方について

アルゴ式でこの問題を解いた際に生じた疑問点と、その解説。

1. はじめに

アルゴ式という学習サービスで、再帰関数を用いてグラフ(正確には木)を探索する問題を解いた。

algo-method.com

その際、特におかしい箇所が見当たらない(コンパイラもエラーを吐かなかった)にも関わらずTLE(制限時間超過)となってしまった。

参考に、最初に書いたコードを示す。必要ない部分は一部省略している。

#include <bits/stdc++.h>
using namespace std;

using Tree = vector<set<int>>;

void paint(Tree t, int v_now) {
    cout << v_now << " ";
    for (int v_child : t[v_now]) {
        paint(t, v_child);
    }
}

int main() {
    int n;
    cin >> n;

    // 木の作成
    Tree t(n);
    int p;
    for (int i = 1; i < n; ++i) {
        cin >> p;
        t[p].insert(i);
    }

    // 探索
    paint(t, 0);
}

2. 原因の調査

いろいろ考えたが正解できなかったため、ほかの方のコードを眺めてみたところ、「再帰関数に引数を参照渡ししているか、値渡ししているか」が異なることがわかった。
そのため参照渡しするように改善した ―― 先ほどのコードでいえば、再帰関数void paint(Tree t, int v_now)をvoid paint(const Tree& t, int v_now)とした ―― ところ、一発で正解することができた。

3. なぜ参照渡しにしたら改善できたか

値渡しだと、グラフTreeをコピーする必要が生じる。グラフが小さければ問題ないが、巨大なグラフの場合、コピーにかかる時間が無視できないほどに増加してしまい、結果としてTLEとなってしまう。
しかし参照渡しの場合、値のコピーが必要なくなるため、値渡しのような事態にはならず、TLEを阻止できる。

具体的にどれほど実行時間がかかるかについては、以下リンクの「無駄なコピーを減らす」の項が参考になる。
atcoder.jp

4. その他参考資料

値渡し/参照渡しの問題点について
www.aerith.net