この記事はProlab Advent Calendar 2015 - Adventarの5日目です。
前の記事があまりに酷かったので差し替えました。
【宣伝】大人気アニメ ゆゆ式のBlu-ray Boxが好評発売中！！
www.amazon.co.jp
概要
みなさん、再帰を使ったプログラム書けますか？
僕は書けません。
特に、プログラミング始めたての人だと再帰で詰まったりするんじゃなかろうかと思います。
再帰とは関数内で自分自身を呼び出すテクニックのことです。not 再起。
このテクニックについて習ったばっかりのころは「こんなのどこで使うんだ！」と思うかもしれませんが、アルゴリズム的な部分、特に「探索」ではよく使います。
再帰関数は、終了条件をどうするか、どこで再帰させるか、引数には何を渡すか、などいろいろ考えることがあって組むには慣れが必要だと思います。
そこで今回おすすめするのが「Scheme」という言語です。
Schemeについては2ヶ月前ぐらいから大学の授業でかじっている程度なので細かい間違いはご容赦ください。
なぜSchemeなのか
SchemeはLISPの方言のひとつです。
関数型言語です（多分）。
関数の適用によってプログラム作ろうぜ的な感じの思想だと思いますが詳しいことは知りません。ググってください。
さて、なぜ再帰に慣れるためにSchemeなのかというと、この言語、C言語などの手続き型言語には標準搭載されているfor文やwhile文といったループの構文が存在しないのです。
関数型だから仕方ないね。
しかし、例えば1から100までの総和を計算するといったループ処理は必要になることが多いです。
ではどうするか。
再帰です。
Schemeではループの代わりに再帰を使います。むしろ再帰なしではプログラムを作れないと思います。
つまり、Schemeをやれば嫌でも再帰を使うことになり、再帰に慣れるということです。
やったね！
例
それではSchemeのプログラムの例を見てみましょう。
まずは定番の階乗の関数から
(define (fact n) (if (= n 0) 1 (* n (fact (- n 1))))
詳しい文法の説明は省略しますが、Schemeでは
(関数の名前 引数1 引数2 ...)
とすることで関数を呼び出すことが出来ます。
また、
(define (関数名 仮引数1 仮引数2 ...) 関数の本体)
とすることで、関数を定義できます。
上の例だと、ひとつの引数nを受け取る関数factを定義しています。
この関数の本体ではifという関数を呼び出しています。
ifは、第1引数を評価した結果が真ならば第2引数を評価した結果を、偽ならば第3引数を評価した結果を返す関数です。
つまり、nが0のとき1を返し、それ以外のときは引数をn-1として再帰し、その結果にnをかけた値を返します。
これは階乗の定義そのものですね。
次に、1からnまでの2乗和を計算する関数です。
C言語で書くなら迷わずfor文を使いますが、Schemeだとこんな感じです。
(define (square-sum n) (if (= n 0) 0 (+ (* n n) (square-sum (- n 1)))))
コンパクトで良いですね。
Schemeにはリストというデータ構造があり、その処理をすることがかなり多いです。C言語でも作れる連結リストと同じ感じです。
面倒なので詳しい説明は省略しますが、例えばリストの長さを計算する関数も再帰です。
(define (llen lst) (if (null? lst) 0 (+ 1 (llen (cdr lst)))))
リストの中から偶数だけを取り出したリストを作る関数も再帰です。
(define (even-list lst) (cond ((null? lst) '()) ((even? (car lst)) (cons (car lst) (even-list (cdr lst)))) (else (even-list (cdr lst)))))
