Subscribed unsubscribe Subscribe Subscribe

SE Can't Code

A Tokyo based Software Engineer. Not System Engineer :(

複雑なプログラムは納得するものではない.

プログラムを書くようになってから数年経つが、初心者でひたすらいろんなコードを真似て書いていた頃に一番感動的だったものは再帰処理だった。関数自身がその関数を呼び出す、入れ子のような処理なのだが、初めてこれを組んだ時は頭の中で想像出来ない無数のパターンをコンピュータが適切に実行して返してくれる様が初心者心に響いた記憶がある。

ただ同時に自分の中で歯痒さもあった。再帰処理を書くたびに紙とペンを用意して、何度も何度もトレースを試みるが、再帰呼び出しの深さが深ければ深いほどトレースはとても難しく途中で断念することが何度もあった。単純なプログラム(直線的に上から下へ落ちていくようなプログラム)であれば、頭の中でプログラムの実行状況をトレースすることはとても簡単だろう。それが複雑な処理になると途端に頭が追いつかなくなってくる。その顕著な例が再帰処理だった。

再帰処理はインプットとなるデータに依存するため、実行状況を想像することはかなり難しい。理屈は理解しているので、どういう結果が返ってくるかはわかるが、実行状態一つ一つに納得出来るかというとまた別の話になる。

たとえば、下記のようなプログラムはどうだろう。よくある簡単な部分和問題だ。

int a[MAX_N];
int n, k;

bool dfs(int i, int sum){
    if (i == n) return sum == k;
    if (dfs(i + 1, sum)) return true;
    if (dfs(i + 1, sum + a[i])) return true;

    return false;
}

void solve(){
    if (dfs(0, 0)) printf("Yes\n");
    else printf("No\n");
}

このプログラムでは与えられた整数n個に対して、いくつかを選択し、その和がちょうどkとなり得るかどうかを判定している。このように再帰を用いて行う深さ優先探索は、一番はじめの状態から遷移を繰り返すことにより、辿り着くことのできる全ての状態を生成することができる。全ての状態遷移を簡単にイメージすると、ループ文が思い浮かびそうだが、再帰を使ってもこうした問題を解くことが可能になる。ただ、ループ文とは違い、再帰はとても実行状態を想像することが難しい。まず僕自身はこの問題を初めて見た時、理屈はわかるがどうも腑に落ちず、ひたすらトレースしたことを覚えている。

こうした複雑な処理は納得することをやめて、キチンとテストを書いて処理の動作を確認したら次に行くことが大事だと思う。とにかく毎度毎度トレースをしていたら日が暮れてしまう。再帰処理なんて深ければ深いほどトレースなんて不可能になっていくので、インとアウトの確認をキチンとやるだけで問題はない。プログラムが正確に定義されて、正しく動作することを確認出来れば、そのプログラムは問題はないと言える。

こうした複雑なプログラムを人間の頭で計算するのは限界があると思うので、理屈を理解して、テストを書いて、問題が無ければ先へ進むことが大事なんじゃないかと最近よく思う。

Remove all ads