e-learning、オラクル研修、LMS(学習管理システム)のiStudy

e-learning、オラクル研修、LMS(学習管理システム)のiStudy

第78回 「『再帰コール』~プログラムの中で自分自身をコールする~」

2013.11.25

こんにちは。インストラクターの蓑島です。

最近、運動不足気味で、筋肉を鍛えなければ・・と思っております。
もう若くありませんが、若い頃から体と頭を鍛える必要性を感じるこのごろです。

さて、皆さんは「再帰コール」をご存知ですか? 
再帰コールとは、今回のタイトルにあるように、プログラムの中で「自分自身をコールする」ことをいいます。再帰コールは多くの言語でサポートされていますが、すべての言語で可能というわけではありません。
例えば、有名なCOBOL言語では再帰コールはできません。PL/SQL言語ではもちろん可能ですが、しかしPL/SQLで再帰コールが可能であることをご存知ない方も多いのではないでしょうか?

再帰コールを使うと、内容によってはたいへんシンプルで美しく短いロジックとなることがあります。
一般的に同じパターンの何かの処理を繰り返す(ループする)とき、再帰コールが可能であることが多く、しかもその場合、ループ処理の記述ではないので、短くシンプルなものになります。

例えば、わかり易い例として、1からNまでの数値を足し算した結果を返すファンクションを考えてみましょう。
よくプログラムの教本にでてくる内容ですね。こういった場合、普通はプログラムの中で変数をもち、その変数にループ処理で1からNまでの数値を加算します。
では、そのような普通のループ処理のファンクションを「FUNC1」という名前で作成してみましょう。
以下のような内容となります。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
CREATE OR REPLACE FUNCTION FUNC1 ( N IN NUMBER) RETURN NUMBER
/**************************************************************/
-- 普通のループ処理で、1からNまでの足し込みを行うファンクション
/**************************************************************/
IS
/**************************************************************/
--   変数の宣言
/**************************************************************/
    V1  NUMBER := 0;
BEGIN
/*************************************************************/
-- 1から引数Nまで、カウンターIの値を変数に足し込む
/*************************************************************/
    FOR I IN 1..N LOOP
        V1 := V1 + I;
    END LOOP;
/*************************************************************/
--  ループ処理が終わったら、その変数の値をリターンする
/*************************************************************/
    RETURN V1;
END FUNC1;
/
 
ファンクションが作成されました。

では早速このファンクションで、1から10まで足し込んだ値、すなわち「FUNC1(10)」をコールしてみましょう。
このファンクションはデータベースの表など更新していないので、SELECT文からコールできます。よって簡単に結果を確認できます。

1
2
3
4
5
SELECT FUNC1(10) FROM DUAL;
 
  FUNC1(10)
----------
         55

ご覧のように、1から10まで足し込んだ値、1+2+3+4+5+6+7+8+9+10 = 55がリターンされましたね。
正しい結果です。

では、今度はこのFUNC1ファンクションの処理を再帰コール的に考えてみましょう。とても単純な考え方です。以下の式がその考え方を表しています。

  FUNC1(10) = FUNC1(9) + 10

この式の意味は1から10まで足しこんだ値(つまり、FUNC1(10) ) は、1から9まで足し込んだ値(つまり FUNC1(9) )に 10を足したものであるという意味です。当たり前のことを言っていますね。

これを一般化して、1からNまで足し込んだ値をFUNC1(N)とすると、以下の式が成立します。

FUNC1(N) = FUNC1(N-1) + N

これをプログラムに当てはめれば、FUNC1(N)の処理は、 「FUNC1(N-1) + N 」をリターンするものである、ということになります。

そうすると、FUNC1(10)をコールすると、FUNC1(9) + 10 がリターンされ、このFUN1(9)の値を決めるためには、FUN1(8)+ 9がリターンされ、その値を決めるためには、FUN1(7)+8がリターンされ・・・・、というように、どこまでも一つ小さい引数(つまり N-1)で、自分自身をコールすることになります。
つまり無限に再帰コールが連鎖します。
それではいけないので、何かの条件で再帰コールをやめる必要があります。

それは、上記の処理の場合、N=1となったとき、つまりFUNC1(1)をコールするときは、「FUNC1(0) + 1」 をリターンするのではなく、「1」をリターンするようにしてあげればいいわけです。あるいは、N=0となったとき、つまりFUNC1(0)をコールするときは、「FUNC1(-1) + 0」をリターンするのではなく、「0」をリターンする考え方もあります。
どちらでもいいのですが、今回は前者にしましょう。
そうすると、Nが1の時は、「1」をリターンし、Nが1より大きいときは、「FUNC1(N-1) + N」をリターンする記述になります。
これにより、N=1のときに、再帰コールの連鎖が止まることになります。

では早速、そのような形に書き換えてみます。
FUNC1ファンクションは比較のため残しておきたいので、ファンクション名を変えて、FUNC2という名前で新規で作成します。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
CREATE OR REPLACE FUNCTION FUNC2 ( N IN NUMBER) RETURN NUMBER
/**************************************************************/
-- 再帰コールで、1からNまでの足し込みを行うファンクション
/**************************************************************/
IS
BEGIN
/*************************************************************/
-- Nが1の時は「1」を、それ以外は、「FUNC2(N-1) + N」 をリターンする
/*************************************************************/
    IF N = 1 THEN
       RETURN  1;
    ELSE
       RETURN FUNC2(N-1) + N;   -- 再帰コール
    END IF;
END FUNC2;
/
 
ファンクションが作成されました。

FUNC1のコードと比べると、FUNC2はずいぶんとシンプルになりましたね。10行目から14行目が説明したとおりの記述です。
すなわち、Nが1の時は、「1」を返す。それ以外の場合は、「FUNC2(N-1) + N」 を返すわけです。

では早速、検証してみます。

1
2
3
4
5
SQL> SELECT FUNC1(10),FUNC2(10) FROM DUAL;
 
  FUNC1(10)  FUNC2(10)
---------- ----------
         55         55

FUNC1(10)も、FUNC2(10)も同じ結果ですね。つまり、1+2+3+4+5+6+7+8+9+10=55 ということで、結果は正しいです。

以下の説明もご覧ください。
再帰コールを行うFUNC2の処理の流れを説明しました。解説のため小さな数にしました。矢印の右側の数字(①,②,③・・)の順番に処理が行われています。

1
2
3
4
5
6
7
8
9
10
SELECT FUNC2(3) FROM DUAL;
 
   FUNC2(3)
----------
          6
 
※上記の問い合わせは以下のように処理されている
    FUNC2(3) = FUNC2(2) + 3              ↓①  ↑⑥ 1+ 2+ 3 = 6
               FUNC2(2) = FUNC2(1) + 2   ↓②  ↑⑤ 1+ 2
                          FUNC2(1) = 1   ↓③  ↑④ 1

いかがですか? とても、簡単で面白いと思いませんか。
再帰コールは人間の自然な感覚(ループ処理)とは少し違う発想がベースになっているので、最初のうち戸惑うかもしれませんが、この例のようにそれがうまく当てはまる状況であれば決して難しいものではありませんし効果的です。
ぜひいろいろと試してみてください。

なお、FUNC2のソースコード13行目「RETURN FUNC2(N-1) + N;」の記述を足し算ではなく、掛け算にして、「RETURN FUNC2(N-1) * N;」とすると、もうお分かりのように、1*2*3・・*Nの計算、つまり、Nの階乗(N!)を計算をするファンクションとなるわけですね。

今回の説明だけだと、プログラム上の遊びのようなもので、実用性を実感できないかもしれません。
次回はデータベースの表を使ったもう少し実用的な再帰コールの例を紹介したいと思います。今度はファンクションではなく、プロシージャで再帰コールをしてみようと思っております。

それでは、次回、ご期待ください。

先頭へ戻る