Yet Another Haskell Tutorial (和訳): 3.7 再帰呼び出し

3.7 再帰呼び出し

CやJavaのような命令的言語でもっとも基本的な制御構造は (for などの) ループである。しかし、forループは破壊的更新を必要とするためHaskellではあまり意味を持たない。その代わりに、Haskellでは再帰呼び出しを使用する。
関数がそれ自身を呼び出すとき、その関数は再帰的であるという (詳細は付録Bを参照)。再帰的関数はCやJavaにも存在するが、関数型言語に比べれば使われることが少ない。典型的な再帰的関数は階数関数だ。命令的言語では、再帰的関数を以下のように書くかもしれない。

int factorial(int n) {
int fact = 1;
for (int i=2; i <= n; i++)
fact = fact * i;
return fact;
}

このコードは正の整数については階数の値を正常に計算するが、階数の基本的な定義をいくつか無視している。階数は通常、以下のように定義される。

この定義自体が再帰的な定義となっている。つまり、n! の値が (n – 1)! の値に依存している。! を関数としてとらえるなら、! は自分自身を呼び出していることになる。この定義はほぼ一字一句Haskellコードに変換できる。

factorial 1 = 1
factorial n = n * factorial (n-1)

おそらくこれより簡単な再帰的関数を見たことがないだろうが、これは文法的に正しい。

■注■ もちろん、再帰呼び出しを命令的に記述することもできる。

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

しかし、おそらく C でループを使うよりもずっと遅いだろう。

再帰呼び出しは習得しにくい場合がある。再帰呼び出しは数学的帰納法の概念と酷似している (付録Bで、この問題について詳細に扱っている)。しかし通常は、1つまたは複数の初期値と、1つまたは複数の再帰的定義を持つものとして問題を考えることができる。階乗の場合、初期値が1つ (n = 1 の場合) と、再帰的定義が1つ (n > 1 の場合) ある。独自の再帰的アルゴリズムを設計する場合、この2つを変えてみると役立つことが多い。
ここで、累乗の処理に話を移そう。2つの正の整数aとbがあったとき、a^bを計算したい。この問題には、初期値が1つある。つまり、bが1のときだ。そして、b > 1 の場合が再帰的定義となる。一般形は以下のように書ける。

これもHaskellコードに直接変換される。

exponent a 1 = a
exponent a b = a * exponent a (b-1)

整数に対する再帰的関数を定義するのとまったく同様に、リストに対する再帰的関数を定義できる。この場合、初期値は通常空のリスト [] で、再帰的定義はリストのコンス (つまり、別のリストにコンスした値) である。
リストの長さを計算する場合を考えてみよう。これもまた2つに分けることができる。リストが空の場合と空でない場合だ。明らかに空のリストの長さは0だ。また、コンスリストの場合は、このリストの長さは第1要素を除いたリストの長さに1を加えた値に等しい。したがって、長さを求める関数は以下のように定義できる。

my_length [] = 0
my_length (x:xs) = 1 + my_length xs

■注■ 以下、Haskellの標準関数に別の定義を与える場合は、必ず関数名の先頭にmy_をつけてコンパイラが混乱しないようにする。

filter関数も同様に考えることができる。これもやはり、初期値は空のリストで、再帰的定義はコンスリストだ。ただし今回は、特定の述語が成立するかどうかに応じてその要素を破棄するかどうか選択する。フィルタ関数は以下のように定義できる。

my_filter p [] = []
my_filter p (x:xs) =
if p x
then x : my_filter p xs
else my_filter p xs

このコードでは空のリストを与えると単純に空のリストを返している。というのも、フィルタは要素を取り除くだけで、加えることはありえないからだ。
(x:xs)という形のリストに対しては、値xを削除するかどうか判断する必要がある。そのためにif文と述語pを使う。p xが真なら、xで始まり、第1要素を除いたリストをフィルタリングしたものが続くリストを返す。p xが偽なら、xを取り除き、第1要素を除いたリストをフィルタリングしたものを返す。
mapや2つの折りたたみ関数も明示的な再帰呼び出しを用いて定義できる。mapの定義は演習を、折りたたみ関数の定義は第7章を参照のこと。

演習

演習 3.7 フィボナッチ数列は以下のように定義される。

正の整数nをパラメータにとり、F_nを計算する再帰的関数fibを書け。

演習 3.8 2つの正の整数aとbをとり、a*bを返す再帰的関数multを定義せよ。ただし、加算のみを使用すること (つまり、乗算を使用することを禁ずる)。まずは、前問およびこの節の残りの部分のように数学的定義を書くこと。

演習 3.9 標準関数mapとは独立に動作する再帰的関数my_mapを定義せよ。

---

前ページ「3.6 コメント」
次ページ「3.8 対話処理」

---

表紙

目次

1 はじめに

2 スタートガイド

3 Haskell言語の基礎

4 型の基礎

5 Basic Input/Output

6 Modules

7 Advanced Features

8 Advanced Types

9 Monads

10 Advanced Techniques

A Brief Complexity Theory

B Recursion and Induction

C Solutions To Exercises

---

これは、Haskell (ハスケル) のチュートリアル "Yet Another Haskell Tutorial" を日本語に翻訳したものです。
オリジナルのドキュメントは、
http://www.cs.utah.edu/~hal/docs/daume02yaht.pdf
などから入手できます。
日本語訳に関するご指摘は、コメントとしてお寄せください。