Schemeチュートリアルの内容をゴリゴリ写経してます。
基本的な制御構造が繰り返しでなく再帰のため、初っぱなから再帰の洗礼に見舞われてます。
ということで再帰関数について調べたことについて書いてみます。
再帰関数とは
再帰関数とは関数それ自体が自らを呼び出す処理を持つ関数のこと。
例えば階乗の計算なんかがよく例として挙げられる。
(define (fact n)
(if (= n 1)
1
(* fact (- n 1)))))
上記の関数factは関数本体からfact自身を呼び出している。
factに渡す引数は1ずつ減算されていて、n=1となったところで再帰処理の終端に到達する。
再帰処理を関数として記述するときは終端の設定を必ず行う(そうしないと無限ループに陥る)。
Flat recursion
リストのトップレベルのアイテム(アトム)を処理対象とする再帰処理をFlat recursionという(この語に関して日本語訳が見つからなかった)。
例えば下記のようなリストのトップレベル要素のみの総和を計算する関数が挙げられる。
;Flat recursion
(define (sum_list l)
(if (null? l)
0
(+ (car l) (sum_list (cdr l)))))
Deep recursion
Flat recursionとは対照的に、リストの要素全てを処理対象とする再帰処理をDeep recursionという。
Deep recursionバージョンのsum_listを示すと下記のようになる。
;Deep recursion
(define (sum_list l)
(cond ((null? l) 0)
((number? l) l)
(else (+(sum_list (car l)) (sum_list (cdr l))))))
Tail recursion(末尾再帰)
関数の末尾が再帰呼び出しのみで終わっている再帰処理を末尾再帰という。
末尾再帰で階乗を計算する関数を書くと以下のような形になる。
;Tail recursion version
(define (fact n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))
この方法だと、引数に計算結果を渡しているので、計算の途中経過を再帰呼び出しの都度保存しておく必要が無い。そのため、末尾再帰を利用することでメモリの消費量を抑えることができる(らしい)。
…とりあえずこんな感じか。
現状、用語の確認がメインみたいな感じですな。
まだ実用的なプログラムに触れてないので、イマイチ再帰の効用について理解できてないのがちょっと。。
Schemeはリスト構造を基本に構成されているので、木構造のデータ(xmlとか)処理なんかが強いんだろうな、とかそのくらいの認識
Github漁って色んなコードを読んでみるべきかなー。