どうも！リョクちゃです。
今回は、VB.Netで再帰処理に関するアルゴリズムについて考えてみます。
ちなみに前回はこちら
目次
再帰処理
再帰はリカーシブ(recursive)といわれ、手続きや関数の中で、
自分自身を呼び出す関数のことをいいます。
例えば、10進数を2進数に変換する記事の中で紹介した関数も
再帰処理を行う、関数になっていました。
これを再帰関数と一般的には呼ばれます。
実際に関数をフローチャートで表したのを以下に示します。
引数が割り切れるまで自身を呼び出し、処理を行っていきます。
こうした処理はほかにも、学生時代に数学の授業で触れるnの階乗についても
再帰処理を用いて答えを導き出すことができます。
階乗とは
数学において非負整数 n の階乗（かいじょう、英: factorial）n ! は、1 から n までのすべての整数の積である。例えば、
である。空積の規約のもと 0! = 1 と定義する。
である。と解説されており、n!と記述することで階乗を表すことができます。
n!は次のようにして求めることができます。
とすることで、n!と(n – 1)!の積で求めることができます。
最終的には、この計算が0!になるまで続きます。
例えば、n=3としたときは、上述の式に当てはめると
$$3! = 3 × ( 3 – 1) × (3 – 2 ) × (3 – 3)$$
$$= 3 × 2 × 1$$
$$= 6$$
となります。
階乗の計算を関数化
階乗の計算を関数化してみると、以下のようになります。
※階乗 プログラムで検索すると、先駆者の方々が様々な書き方をされていますので、
気になる方はお調べください。
|
1 2 3 4 5 6 7 8 9 |
Private Function factorial(ByVal n As Integer) As Integer Dim rec As Integer If n > 0 Then rec = n * factorial(n - 1) Else rec = 1 End If Return rec End Function |
nが0以上の時は、n × factorial(n – 1)が呼び出され、
nが0の時は変数recに1を代入しています。
n = 3であれば、
n > 0なので、
|
1 |
3 * factorial(3 - 1) |
factorial()の中身は2になります。
|
1 |
3 * factorial(2) ' → 6 |
続いて、
|
1 |
2 * factorial(1) ' → 2 |
といった順番で自身を呼び出しながら最終的な解を導き出していきます。
ここで条件式のn > 0を本来とは異なる条件式にしてしまうと、
無限ループに陥ってしまうので気を付けましょう。
まとめ
再帰処理は、
- 自分自身を呼び出す関数のこと
- 終了条件が間違っていると無限ループなどに陥る
- 呼び出し過ぎに注意(メモリが飽和状態になってしまう)
以上のことに気を付ければ、再帰処理は非常に使いやすい手法になります。
再帰処理は、情報系の試験では出題される頻度も高いので、
これを機にこんなものだよとイメージでもつかんでいただければ嬉しいです。
最後までご覧いただきありがとうございます。
・こちらの書籍を参考にVB.Net勉強しています。
