再帰関数ってなんだろう？

AutoLISP に限らずプログラミング言語の説明には再帰関数というものが出てきます。プログラミング初心者にとっては聞き慣れないため難しいものだと思われるかもしれませんが、取り組んでみるとそう難しいものではありません。再帰関数について検索してみると、他に多くの説明したページが見つかりますが、ここでもあらためて説明をしてみたいと思います。再帰関数の入り口のイメージは、高校数学で習う数列をプログラムで表すテクニックです。

数列はどのように表されたでしょうか？例として、初項 3 公差 5 の等差数列を見てみます。以下のような数列になります。

これを数学らしく書きますと次のようになります。

このような数列の An の値を求める関数を作ってみます。もっとも今回のような問題は An = 5 (n-1) + 3という式から計算できますが、あえて上の定義に沿った形で計算します。 再帰関数のテクニックを使わない場合は、while でループする構造になります。初項の値を元に、回数を数えながら公差を加えていきます。

(defun TousaSuuretu-1 (n / count An)
  (setq An 3                            ; 初項
        count 2
  )
  (while (<= count n)
    (setq An    (+ An 5)                ; 公差を加算
          count (1+ count)
    )
  )
  An
)

もちろんこれで出来上がりとしても良いのですが、再帰関数の形式にすると次のように書き表せます。

((defun TousaSuuretu-2 (n)
  (if (= n 1)
    3                                   ; 初項
    (+ (TousaSuuretu-2 (1- n)) 5)       ; 公差を加算
  )
)

いかがでしょうか？すいぶん簡単になったように見えます。しかも、先ほど数学らしく数列を書き表したものをそのままプログラム言語で書き直したようでもあります。数学風に書き表した An は An-1 の値を利用して定義されたのと同じように、(TousaSuuretu-2 n) を求めるのに (TousaSuuretu-2 (1- n)) の値を使っています。ここでは関数の中から引数を変えて自分自身を呼び出す構造になっています。このような構造を持つものを再帰関数と言います。自分自身を再帰的に呼び出すのに引数を変える、そして引数がある条件、今回の場合は n=1 になると再帰を行わないというのがポイントです。そうでなければ無限に自分自身を呼び出す無限再帰というエラーが起こります。

上の再帰関数は n = 3 の時は、次のような計算を経て答えが求まります。

再帰関数は、数列のような構造をもつ問題、数学の言葉を使うと漸化式（ぜんかしき）を含む問題にはたいへん効果的です。

再帰関数の使い道

普通のプログラミング言語では説明はここで終わりです。手続き型言語を使っている場合は、再帰関数を使う機会はあまりないと思います。しかしながら LISP をはじめとした関数型言語は再帰関数を好みます。LISP のリストは再帰関数と相性がとても良いのです。リストのような複数のデータの塊を処理する際に、while でループを組むより上で見たように再帰関数に置き換えて書き表します。

例えば、文字列が並んだリストを改行しながら表示する例を考えますとループを使うと次のように書けます。

(defun prompt-list-1 (slist / count)
  (setq count 0)
  (while (< count (length slist))
    (terpri)
    (prompt (nth count slist))
    (setq count (1+ count))
  )
)

これを関数型言語では、次のように再帰関数で書くことを好みます。

(defun prompt-list-2 (slist)
  (if slist
    (progn
      (terpri)
      (prompt (car slist))
      (prompt-list-2 (cdr slist))
    )
  )
)

実行例は以下の通りです。

コマンド: (prompt-list-2 '("Pen" "Pinaple" "Apple" "Pen"))⏎
Pen
Pinaple
Apple
Pennil

実行の経過は次のように進みます。

他のプログラミング言語に比べて関数型言語では再帰関数がよく使われる、比重の大きなテクニックです。