再帰呼び出しはよくわからないとお嘆きの皆さんへ

再帰呼び出しはどうして難しいと思われているのか

　プログラミングを習うと、後半の方で再帰呼び出しというのが出てきます。説明はわかったような気はするが、どうもしっくりこない。何とか読めるけど，書ける気がしない、とお嘆きの皆さんは多いのではないでしょうか。私は学部2年次にPascal言語で，3年時にLisp言語で再帰呼び出しを2回、講義で習いましたが、どうもしっくりと来なかった。後から分かりましたが、それには理由があったのです。まずPascal, C, Javaような手続き型言語で再帰呼び出しを習うと、後述する「コツ」がわかりにくい。それから、私が3年時に習ったLispはM式という、構文上，手続き型言語に近くしたもので，これもかえってLispの本質を分かりにくくしていました。

　再帰呼び出しは実は難しくありません。ついでに言うと、Lispも難しくありません。なぜここでLispを持ち出すかと言うと，Lispにはいろいろな種類がありますが、元々Lispは単純性を極めた言語で、ループは再帰呼び出しを用いて表現します。余計な事が入っていない分，再帰呼び出しの本質を理解するのにちょうどよいのです。

　それから、再帰呼び出しと代入による副作用を両方同時に用いると、頭がこんがらがります。再帰呼び出しの基本を学ぶときは，副作用なしにして、本質をしっかりと頭に入れるのが、近道です。また、これが先に述べた，手続き型言語で再帰呼び出しを学ぶとわかりにくいということの理由です。

　再帰呼び出しにはちょっとしたコツがあり、このコツをマスターすると、おそらく誰でもスラスラと再帰呼び出しのプログラムを書けるようになります。再帰呼び出しは強力なツールです。再帰呼び出しをサポートした言語であれば，すべてのループは再帰呼び出しに書き直せますが，その逆は必ずしもできません。以下に述べるコツを覚えれば，ループを書くがごとくサラサラと再帰呼び出しのプログラムが書けるようになると思います。

SchemeというLispの一方言の紹介

　再帰呼び出しのやり方を説明するために、SchemeというLisp言語の一種を使います。以下では，SchemeやLispを全く知らなくてもわかるように説明します。

　Schemeで再帰呼び出しを説明するのに必要な構文はたった3つだけ。まずは関数定義と関数呼び出しです。

(define (add a b) (+ a b))

(add 3 2)

　ここではaddという名前の関数を定義しています。a, bは仮引数です。定義内容は(+ a b)すなわちa+bです。Schemeでは式の記述をすべて前置記法(prefix notation)だけで行います。演算子や関数名が引数よりも前にあるという意味です。数学や，CやJava言語等の多くのプログラミング言語で使われるa+bというような表現yは，中置記法(infix notation)と呼ばれます。

　上の例では、(add 3 2)で、定義した関数addを呼び出しています。結果は5です。

　もう一つは条件式であるif式。

(if (= 1 1) 1 0)

　上の式では，1=1であれば1、そうでなければ0を返しています（結果は1）。

再帰呼び出しの基本形（線形再帰）

　関数定義とif。この二つを使って，階乗(n!)を計算するSchemeのプログラムを書いてみます。

(define (fact1 n)
  (if (= n 0)
       1
     (* n (fact1 (- n 1)))))

　前項の3つの機能、すなわち、関数定義，関数呼び出し，ifだけでプログラムが書けていることを確認して下さい。

　上記のパターンは線形再帰形という一つのパターンになっています。上記のプログラムは実行時にn*(n-1)*(n-2)*...*1という式を実行時に作り出し，その式を計算させています。再帰呼び出しは，実行時に（計算）式，プログラムを動的に作り出しそれを計算することに相当しているのです。作り出せるパターンは無限にありますが、特にn*(n-1)*(n-2)*...*1のように直線的に式を構成しているので，この形は線形再帰形と呼ばれています。後述する，一般的な1重ループに相当します。

　上記のプログラムは，階乗計算の定義と実質同じになっていることにも着目しましょう。

0! = 1
n! = n*(n-1)!

　数学の式はしばしば再帰的に定義されます。というか、数学では，（破壊的）代入とか、ループという概念は本来なく、繰り返し的なことは再帰を用いて定義しているのです。高校数学でならった数列を思い出しましょう。例えば次のような。

a[0] = 1
a[1] = 1
a[n] = a[n-1] + a[n-2]

　ちなみにこれは3行目で再帰が2回あり、線形ではない再帰になっています。後述のように線形再帰プログラムは1重ループプログラムに相当しますが，上記のように、一つの式に2回、再帰が現れる場合，それによって構築される「式」は木構造的となり，このままではループを使ったプログラムでは計算できません。

　先のSchemeのプログラムfact1と等価なプログラムは、下記のように書けます。

int fact2(int n) {
  if (n == 0)
    return 1;
  else
    return n * fact2(n - 1);
}

　型宣言とreturn文が必要でない分だけ，Schemeの方がシンプルですね。（カッコに目をつぶれば）

　しかし皆さんは，階乗のような簡単な計算を書くときに，わざわざ再帰を使った、上記のような書き方はしないでしょう。通常は，ループを使って書くはずです。例えば，while文を使って下記のように。

int fact3(int n) {
  int m=1, s=1;
  while (m <= n) {
    s = s * m;
    m = m + 1;
  }
  return s;
}

末尾再帰

　実は、再帰呼び出しには、上記のループプログラムに対応する書き方があります。それを次に示します。

(define (fact4 n) (fact4_iter n 1 1))

(define (fact4_iter n m s)
  (if (> m n)
      s
    (fact4_iter n (+ m 1) (* s m))))

　関数fact4は関数fact4_iterを初期値付きで呼び出しています。fact4_iterはnの値はそのまま、そしてm、sの値を更新するかのように再帰呼び出しをしています。このfact4_iterの再帰呼び出しの形をよく見ましょう。再帰呼び出しではありますが，実質，ループをダイレクトに表現しているのです。
　fact1の再帰呼び出しでは，fact1を再帰呼び出しした後に*演算を施していました。今回はfact4_iterの後にすることはありません。このような形の再帰呼び出しを末尾再帰(tail-recursion)といいます。末尾再帰のプログラムは，通常の手続き型言語のループの書き方に対応した書き方です。そして、最近のほとんどのLispの処理系は，末尾再帰を見つけると，実行時には再帰呼び出しをせず、ループと同様の処理をする処理を内部でしてくれます。このため、計算を後ですることを記憶するための仕掛け（スタック）を使わずに済み，手続き型プログラムにおけるループと同様の効率で実行されます。

　後に示したSchemeのプログラムで，Cでは一つの関数で済むところ，Schemeでは二つの関数(fact, fact_iter)を書かねばならないことにちょっと違和感を感じる人がいるかもしれません。Schemeでは、次のように，関数内にローカルな関数を書くことで，一つの関数定義のように見せることができます。

(define (fact5 n)
  (define (fact5_iter m s)
    (if (> m n)
        s
        (fact5_iter (+ m 1) (* s m))))
  (fact5_iter 1 1))