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

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

再帰関数

pointこの用語のポイント

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

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

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

スポンサーリンク

簡単に書くよ

再帰関数とは

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

image piyo

詳しく書くよ

順番に見ていきましょう。

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

再帰関数

関数」についても、説明しておきます。
関数は「何かを入れると何かを計算して何かを返してくれるプログラムの部品」です。
一般的には、入力を受けて処理を行い、その結果として出力があります。

再帰関数2

それを踏まえて、一人合わせ鏡状態になっている関数が「再帰関数」です。
「自分自身を呼び出す処理が書かれている関数」を指します。

再帰関数3

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

1.ミカン箱を受け取る

2.ミカンを1個食べる

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

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


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

再帰関数4

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

再帰関数5

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

再帰関数6

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

再帰関数7

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

再帰関数8

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

再帰関数9

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

再帰関数10

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

再帰関数11

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

再帰関数12

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

再帰関数13

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

再帰関数14

この話におけるピヨ太関数に相当するのが、再帰関数です。
自分自身を呼び出す処理が書かれている関数を指します。

せっかくなので、もう少しプログラムっぽい例も書いておきましょう。
PHPで書いたサンプルですが、以下の処理で登場する関数「piyota()」が再帰関数です。

<?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.ミカンがなくなったら、終わり


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

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

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

再帰関数15

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

これが

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

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

次に

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

について、説明します。

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

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

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

再帰関数16

でも、待ってください。

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

再帰関数17

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

それと同じです。

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

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

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

これが

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

です。

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

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

あくまで個人的な意見ですが、再帰関数を作らないで済むのであれば、作らないに越したことはないと思います。

なお、再帰関数を呼び出すことを指して「再帰呼び出し」や「再帰処理」と表現します。
ついでなので、併せて覚えてあげてください。

image piyo2

一言でまとめるよ

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

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