Schemeで再帰を行う
※ 以下はScheme初心者である私の勉強用のメモです。
間違っている可能性がありますので注意してください。
再帰呼び出し
再帰呼び出しとは、関数が自分自身を呼び出すことである。Schemeでは、ループ処理を再帰を利用して実装することが多いようである。
通常の再帰
例えば、xとnを指定して、xのn乗を計算する再帰関数は以下のように実装できる。
例
;xのn乗を計算する (define (power x n) (if (<= n 0) 1 (*(power x (- n 1))x)))
再帰呼び出しの欠点として、パフォーマンスの低下が挙げられる。
通常計算機は、関数を呼び出す前に計算の途中結果をメモリ上のスタック領域に保持し、関数から抜けた時に解放するため、再帰的に関数を呼び出すと、スタック領域から計算の途中結果が解放されないためである。例えば上記のpower関数を使用して、2の4乗を計算すると、以下のように計算される。
計算のトレース
(power 2 4) = (* (power 2 3) 2) = (* (* (power 2 2) 2) 2) = (* (* (* (power 2 1) 2) 2) 2) = (* (* (* (* (power 2 0) 2) 2) 2) 2) = (* (* (* (* 1 2) 2) 2) 2) = (* (* (* 2 2) 2) 2) = (* (* 4 2) 2) = (* 8 2) = 16
末尾再帰
再帰呼び出しを行う際に、計算の途中結果を引数で渡せば、途中結果をスタック領域に保持しておく必要がなくなるため、効率のよい繰り返し処理を行うことができる。これを末尾再帰(tail call)という。Schemeで末尾再帰を行うと、通常のループと同じ実行速度になるように最適化される。なお、末尾再帰を行ったとしても言語やコンパイラによっては最適化されない場合があるので注意が必要である。末尾再帰の基本的な書き方は以下の通りである。
末尾再帰の基本的な書き方
(define (関数名 引数1, 引数2, ・・・, 引数n, カウンタ, 計算の途中結果) 式・・・)
通常の再帰で例として挙げたpower関数を末尾再帰を使って書き直すと以下のようになる。
例
;xのn乗を計算する (define (power-tail x n ans) (if (<= n 0) ans (power-tail x (- n 1) (* x ans))))
なお、上記のpower-tail関数を使用して、2の4乗を計算すると、以下のように計算される。
計算のトレース
(* (power-tail 2 4) 1) = (* (power-tail 2 3) 2) = (* (power-tail 2 2) 4) = (* (power-tail 2 1) 8) = (* (power-tail 2 0) 16) = 16
named-let
let式を使用して末尾再帰を行うことが出来る。具体的にはlet式に名前を付け、そのlet式のスコープ内で自身を呼び出すことで末尾再帰を行う。
一般形
(let 名前((変数名1 初期値1) (変数名2 初期値2) (・・・ ・・・) (変数名n 初期値n)) 式・・・)
power関数をnamed-letを使って書き直すと以下のようになる。
例
;xのn乗を計算する (define (power-named x n) (let loop((i 0) (ans 1)) (if (>= i n) ans (loop (+ i 1) (* ans x)))))
letrec
letrec式を使用して再起を行うことができる。letrec式は局所的に使用する関数を定義するための式である。
一般形
(letrec ((関数名1 ラムダ式1) (関数名2 ラムダ式2) (・・・ ・・・) (関数名n ラムダ式n)) 式・・・)
例
(define (power4 x n) (letrec ((pow-iter (lambda (i ans) (if (>= i n) ans (pow-iter (+ i 1) (* ans x)))))) (pow-iter 0 1)))
