[ 通常表示 ]  [ 簡易表示 ]  [ シンプル表示 ]

「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典イメージぴよ画像「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

再帰処理

pointこの用語のポイント

point自分自身を呼び出す処理が書かれている関数を呼び出すよ

point終了条件が間違っていると大変なことになるから気を付けてね

point呼び出し回数が多くなるとメモリをいっぱい使うから気を付けてね

スポンサーリンク

簡単に書くよ

再帰処理とは

「再帰呼び出し」と、意味合い的には同じ。
つまり

プログラミングの世界における合わせ鏡みたいなもの
であり

自分自身を呼び出す処理が書かれている関数を呼び出すこと
です。

image piyo

詳しく書くよ

※このページの説明は「再帰呼び出し」の説明と、ほとんど同じです。既に「再帰呼び出し」の説明をご覧になった方は、読んでもあまり意味は無いと思います。「処理」に注目するか「(関数の)呼び出し」に注目するかの違いです。「再帰呼び出し」と「再起処理」は、ほぼ同じ意味で使われます。

みなさんは「合わせ鏡」を知っていますか?
2枚の鏡(A、B)を向い合せに置いたときに起きる現象で、鏡Aの中に鏡Bが写り、鏡Aに写っている鏡Bの中に鏡Aが写り、鏡Aに写っている鏡Bの中に写っている鏡Aの中に鏡Bが写り……と、無限に入れ子になる現象です。

再帰処理

それを踏まえて、自分自身を呼び出す処理が書かれている関数を呼び出すのが「再帰処理」です。

再帰処理2

対象が関数ではなく、プログラムの部品だったり、他の何かだったりする場合も、あるかもしれません。
そこら辺は、ゆるく解釈してください。

とにかく

自分自身を呼び出す処理が書かれている何か

を呼び出すことです。

また「再起処理」ではなく「再帰呼び出し」と表現されることもあります。
意味は同じだと思って構いません。
「処理」に注目するか「(関数の)呼び出し」に注目するかの違いです。

それでは、実際の例を見てみましょう。

例えば、そうですね。
以下の処理を行うピヨ太関数がありました。

1.ミカン箱を受け取る

2.ミカンを1個食べる

3.ミカンが残っていたら、ピヨ太関数(自分自身)を呼び出してミカン箱を渡す

4.ミカンがなくなったら、終わり


ピヨ太関数は、ミカン箱を受け取ります。

再帰処理3

ピヨ太関数は、ミカンを1個食べます。

再帰処理4

ミカン箱にミカンが残っていたら、再度、ピヨ太関数を呼び出します。
このとき、残りのミカンが入ったミカン箱を渡します。

再帰処理5

分かりにくいので、ピヨ太関数から呼び出されたピヨ太関数は「ピヨ太関数2号」と呼びますね。
ピヨ太関数2号は、呼び出し元のピヨ太関数からミカン箱を受け取ります。

再帰処理6

ピヨ太関数2号は、ミカンを1個食べます。

再帰処理7

ミカン箱にミカンが残っていたら、再度、ピヨ太関数を呼び出します。
このとき、残りのミカンが入ったミカン箱を渡します。

再帰処理8

ピヨ太関数2号から呼び出されたピヨ太関数は「ピヨ太関数3号」と呼びますね。
ピヨ太関数3号は、呼び出し元のピヨ太関数2号からミカン箱を受け取ります。

再帰処理9

ピヨ太関数3号は、ミカンを1個食べます。

再帰処理10

おっと、ミカン箱が空っぽになりました。
ここで処理は終了です。

再帰処理11

今回は、ピヨ太関数が3号まで登場しました。
これは、ミカン箱にミカンが3個入っていたからです。

再帰処理12

もしミカン箱に入っているミカンが4個なら、ピヨ太関数は4号まで登場します。
5個なら5号、6個なら6号、10個なら10号まで登場するでしょう。

再帰処理13

このように、自分自身を呼び出す処理が書かれている何かを呼び出すのが、再帰処理です。

せっかくなので、もう少しプログラムっぽい例も書いておきます。
PHPで書いたサンプルですが、以下の処理は再帰処理になっています。

<?php

//-------------------------------
//ピヨ太関数
//-------------------------------
function piyota($mikan = 0){

    // ミカンを食べる
    $mikan = $mikan - 1;

    // 残りミカン数を表示
    print "残りミカン数:" . $mikan . "\n";

    if($mikan > 0){    //残りミカンあり
        //ピヨ太関数を再帰呼び出し
        return piyota($mikan);
    }else{
        //終了
        print "終わり";
        return 0;
    }
}

//-------------------------------
//主処理
//-------------------------------

//最初のミカンの数
$mikan_num = 10;

//ピヨ太関数呼び出し
piyota($mikan_num);


この処理の実行結果は、以下の通りです。

残りミカン数:9
残りミカン数:8
残りミカン数:7
残りミカン数:6
残りミカン数:5
残りミカン数:4
残りミカン数:3
残りミカン数:2
残りミカン数:1
残りミカン数:0
終わり


それっぽく動いていますね。

$mikan_num = 10;

の「10」を変えれば、関数「piyota()」が呼び出される回数も変わります。

再帰処理は、上手く使うと「デキるプログラマ」になった気分を味わえます。
「再帰処理を使いこなしているオレ、かっけー」となるでしょう。

それが罠です。

再帰処理を行う際は、ご注意ください。
再帰処理には、少なからずリスクがあります。

他にもあるとは思いますが、私がパッと思い浮かぶリスクは、以下の2つです。

1.終了条件が間違っていると永遠に処理が終わらない
2.入れ子が深くなると、メモリが足りなくなる


先ほどのピヨ太関数を例に、それぞれ説明しておきます。

まずは

1.終了条件が間違っていると永遠に処理が終わらない

について、説明します。

ピヨ太関数の処理は

1.ミカン箱を受け取る

2.ミカンを1個食べる

3.ミカンが残っていたら、ピヨ太関数(自分自身)を呼び出してミカン箱を渡す

4.ミカンがなくなったら、終わり


でした。
これが、もし

1.ミカン箱を受け取る

2.ミカンを1個舐める

3.ミカンが残っていたら、ピヨ太関数(自分自身)を呼び出してミカン箱を渡す

4.ミカンがなくなったら、終わり


だったら、どうでしょう?

ミカンは食べません。
舐めるだけです。
舐め終わったミカンは、ミカン箱の中に戻します。

この状態でピヨ太関数を実行すると、ピヨ太関数が無限に増え続けます。
ミカン箱のミカンは、絶対になくならないからです。
ひたすら、ピヨ太関数が呼び出され続けます。

再帰処理14

これは大変ですね。
ピヨ太関数が増え続けるだけで、いつまで待っても処理が終わりません。
ピヨ太関数を動かしているコンピュータが力尽きるのが先でしょう。

これが

1.終了条件が間違っていると永遠に処理が終わらない

です。
「間違わなければ、いいじゃん!」と言われれば、確かにその通りですが、ちょっと心配になりませんか?

次に

2.入れ子が深くなると、メモリが足りなくなる

について、説明します。

今度は、ピヨ太関数は正しいピヨ太関数です。
期待通りの処理をしてくれます。

そんなピヨ太関数にミカンが100個入ったミカン箱を渡したら、どうなるでしょう?

そうですね。
ピヨ太関数は100号まで登場します。

再帰処理15

でも、待ってください。

ピヨ太君のお家は、そんなに広くもありません。
100人も入ったら、ピヨ太君が潰れるか、お家の壁が吹っ飛びます。

再帰処理16

いずれにせよ、異常事態ですね。

それと同じです。

関数が実行されるとき、メモリが使われます。
再帰処理の場合、関数を呼び出す回数が多くなれば、使われるメモリの量も増えます。

メモリは有限です。
呼び出される回数が増えれば、いずれメモリを使い尽くすでしょう。
そうなったら、それで試合終了です。

このように、処理としては何も間違っていないにもかかわらず、動かしたときに変なことになる可能性があります。
呼び出し回数を上手く制御すれば問題ない話ではありますが、ちょっと怖くありませんか?

これが

2.入れ子が深くなると、メモリが足りなくなる

です。

今、説明した2つのリスクは、気を付ければ、それで済む話です。
「問題」と言うほど、大げさなものでは、ありません。

ですが、リスクはリスクです。

あくまで個人的な意見ですが、再帰処理を使わないで済むのであれば、使わないに越したことはないと思います。

なお、再帰呼び出しになっている関数は「再帰関数」と言います。
ついでなので、併せて覚えてあげてください。

image piyo2

一言でまとめるよ

まぁ「再帰処理」って単語が出てきたら「自分自身を呼び出す処理が書かれている関数を呼び出すことなんだな~」と、お考えください。

一番上に戻るよ
スポンサーリンク