プログラミングで何度も同じ処理を繰り返し行う方法として再帰処理と繰り返し処理が存在します。
この２つは同じことを繰り返し行うことで処理を行うという共通点があるのですが、繰り返し処理を行う方法が異なります。
今回は再帰処理と繰り返し処理についてコードの例を示しながら違いを説明します。
繰り返し処理の書き方
再帰処理について最初に説明すると理解がややこしくなるのでまずは単純な繰り返し処理について説明します。
繰り返し処理とは決まった回数同じ処理を繰り返すことです。
for文やwhile文を使った書き方が一般的であり、例えばfor文を使って繰り返し処理を書くと以下のような書き方になります。
//繰り返し処理（１からnumまでの和を求める）
public static int sumNum(int num) {
int retNum = 0;
for (int i = 1 ; i < num + 1; i++) {
retNum = retNum + i;
}
return retNum;
}このコードは１からnumまでの値を順番に足していく処理であり、４行目から６行目までにfor文が書かれていて、数字を加算する処理を繰り返しています。
そして、numまで足し終えたらfor文を抜けて値を返します。
今回は繰り返し処理をJavaで書いてみましたが、VB.netやPHPなど、他の言語でも同じ考え方です。
繰り返し処理は一般的に処理を繰り返す場合に使われている書き方で、知らないとまともなコードが書けないくらい必須知識となっています。
プログラムを書くと必ず使う処理なので、しっかりと覚えておきましょう。
while文による繰り返し処理は繰り返し条件を満たし続ける間はずっと処理を行うため、繰り返し条件を有限回で抜けるようにする考慮が必要です。
ちなみに、while文を使った繰り返し処理は以下のようになります。
//繰り返し処理（１からnumまでの和を求める）
public static int sumNum2(int num) {
int retNum = 0;
int i = 1;
while (i < num + 1) {
retNum = retNum + i;
i++;
}
return retNum;
}5行目から8行目がwhile文による繰り返し処理の一連の処理ですが、上記の書き方だと手動でiを加算する処理を入れなければ無限にループし続けます。
プログラミングを勉強し始めた人や経験が浅い人が良くやるミスなので、while文を使う場合は注意が必要です。
なお、while(0)、for(;;)などの書き方をする人が時々いますが、ループの終了条件が分かりにくいため個人的に使用することはオススメしません。
再帰処理の書き方
再帰処理とはメソッド内で同一メソッドを呼び出す書き方です。
例えば以下のようにコードを書くと再帰処理を使って処理を行うことになります。
//再帰処理（階乗を求める）
public static int calKaijou(int num) {
if(num == 0 || num == 1) {
return 1;
} else {
return num * calKaijou(num -1);
}
}このプログラムでは階乗を求めるために例えば5!=5×4×3×2×1という計算をメソッドの再帰呼び出しにより実現しています。
6行目に注目して欲しいのですが、calKaijouメソッドの中でcalKaijouメソッドを呼び出しています。
こうすることで、calKaijouメソッドを再帰的に呼び出して処理を行うことが出来ます。
上記のコードでnumが5である場合、以下の順序でメソッドが呼び出されます。
calKaijou(5)→calKaijou(4)→calKaijou(3)→calKaijou(2)→calKaijou(1)
そして、値が返ってくる場合は以下のような順序で値が返されます。
calKaijou(5)←calKaijou(4)←calKaijou(3)←calKaijou(2)←calKaijou(1)
そして、最後にcalKaijou(5)の値が返されて、処理が終了します。
この処理の書き方には注意点がありますので、次章でお話しします。
再帰処理を使う場合の注意点
再帰処理は同じメソッドを再帰的に呼び出す（つまりメソッド内で同じメソッドを呼び出すことを繰り返す）処理の方法です。
この処理は必ず有限回で終了しないといけません。
つまり、再帰処理を行う上で、どこかでメソッドの再帰呼び出しが終わり、値を返す処理が行われる必要があります。
もし、有限回で終了しない場合、スタックオーバーフローというエラーが起き、強制終了してしまいます。
また、有限回で終了する場合も回数が多すぎるとスタックオーバーフローが起きる可能性があります。
ここでスタックという言葉が出てきましたが、再帰処理では処理をスタック上に順番に入れていき、完了できる処理が出たら、値を返して処理をスタックから取り出す。
そして、順番に値を返していきスタックから処理を取り出すことを繰り返していきます。
スタックは最初に入れたものが最後に取り出されるデータ構造のことで、キューと一緒に説明されることが多く、スタックについての理解がないと、再帰処理が何をやっているのかが今ひとつわかりにくいです。
なので、この記事でスタックとキューについて説明しますので、ここでしっかりとスタックの概念を理解して欲しいと思います。
また、スタックは処理をメモリ上に確保するため、有限回で完了する場合でもメソッドの再帰呼び出しの回数があまり多くならないほうがいいでしょう。
10万回、100万回繰り返し呼び出すような処理であれば、あまり再帰呼び出しを使うことはオススメしません。
また、再帰呼び出しで書くとプログラムが見やすくなりますが、書き方が複雑であればプログラムが何をやっているか追っていくのが難しくなります。
なので、処理が複雑になる、再帰呼び出しの回数が極端に多くなるなどの懸念があれば再帰呼び出しを使わずに、繰り返し処理で何とかできないか検討してみる必要があるでしょう。
まとめ
今回お話ししたことをまとめると以下のようになります。
- 繰り返し処理はfor文やwhile文を用いた一般的な繰り返し処理
- 繰り返し処理でwhile文を使う場合は、必ず有限回で終了するように実装する
- 再帰処理はメソッド内で同一メソッドを呼び出す
- 再帰処理は呼び出しがスタックで管理され、再帰呼び出しの回数が多すぎるとスタックオーバーフローが起きる
- 複雑な処理や呼び出し回数が多い処理の場合、再帰呼び出しを使うことはオススメしない
繰り返し処理、再帰処理はどちらも覚えておくことで柔軟に対応できますが、それぞれ注意点があるのでしっかりとそれぞれの特徴について理解しておきたいものです。
演習問題
今回、階乗を求める処理を再帰処理で書きましたが、これを繰り返し処理で書いてみてください。
演習問題の解答例
階乗を繰り返し処理で書くと以下のように書けます。
//階乗を求める処理を繰り返し処理で書く
public static int calKaijou(int num) {
int retNum = 1;
for (int i = num ; i > 0 ; i--) {
retNum = retNum * i;
}
return retNum;
}出来ましたでしょうか？
もちろんwhile文を使って実装した場合も問題ありません。
また、1から順番に乗算していても問題ありません。
演習が出来た方は、きちんと再帰処理と繰り返し処理について理解できているため、実務にもしっかりと応用して頂ければと思います。
今回の記事はここまでとなります。
また次の記事でお会いしましょう。
