[Prev]    [ Up ]    [Next]

再帰呼出し

リストのように再帰的なデータ構造を扱うには，再帰呼出しを行う関数を用いるのが自然である． ここでは，まず数値を扱う関数を例として，再帰呼出しについて説明する．

0以上のnに対して，xのn乗は，

	x^n = 1           n = 0,
	    = x・x^(n-1)  n > 0

	f(x,0)=1
	f(x,n)=x*f(x,n-1)

	f(x,0)=1
	f(x,n)=f(x,n+1)+1, n > 0
	f(x,n)=f(x,n-1)-1, n < 0

xの累乗を計算する関数をSchemeで書けば以下のようになる．

	(define (expt x n)
	  (if (= n 0) 
              1 
              (* x (expt x (- n 1)))))

	> (expt 2 4)
	;; (* 2 (expt 2 3))
	;; (* 2 (* 2 (expt 2 2)))
	;; (* 2 (* 2 (* 2 (expt 2 1))))
	;; (* 2 (* 2 (* 2 (* 2 (expt 2 0))))
	;; (* 2 (* 2 (* 2 (* 2 1))))
	;; (* 2 (* 2 (* 2 2)))
	;; (* 2 (* 2 4))
	;; (* 2 8)
	16

自己末尾再帰

上の再帰呼出しでは，乗算はその引数の評価が完了するまで行われないため，引数の評価が先に再帰的に行われ，“引数が揃うまで評価が延期されている式”が大量に発生する．またそのため，計算途中で式が膨張する(式が長くなる)． このような再帰呼出しは計算の効率という面では好ましくない．

このように途中の式が膨張する原因は，再帰呼出しが自分自身と他の演算の組み合わせになっていることにある． 再帰的な関数を，自分自身のみを呼び出すことで値が得られるような自己末尾再帰呼出しの形で表すことができれば，中間式の膨張を避けることができる．

そのためには，計算の進行状況・途中結果を示すような状態変数を導入すればよい． xのn乗を自己末尾再帰関数で書き直すと以下のようになる．

	(define (expt-iter x n)
	  ;; 局所関数の定義 : expt-iter-auxは，expt-iterの中のみで有効
	  (define (expt-iter-aux m p)
	    (if (= m 0) 
                p 
                (expt-iter-aux (- m 1) (* x p))))
	  (expt-iter-aux n 1))

expt-iterは，局所関数expt-iter-auxを呼び出す． この局所関数が実際に計算を行う関数であり，自己末尾再帰呼出しの形式になっている． expt-iter-auxの引数m,pがそれぞれ計算の進行状況，途中結果を表す． またこの中でxが現われるが，これはexpt-iterの引数xがそのまま使われる．

(expt-iter 2 4)の計算過程は以下のようになる．

	> (expt-iter 2 4)
	;; (expt-iter-aux 4 1)
	;; (expt-iter-aux 3 2)
	;; (expt-iter-aux 2 4)
	;; (expt-iter-aux 1 8)
	;; (expt-iter-aux 0 16)
	16

	p*2^m = 16

trace,untrace

関数traceを使うことによって，関数の呼出しの状況と返り値を見ることができる．

        ;; scmの場合
        ==> (trace expt)
        ==> (expt 2 4)
        CALL expt 2 4
         CALL expt 2 3
          CALL expt 2 2
           CALL expt 2 1
            CALL expt 2 0
            RETN expt 1
           RETN expt 2
          RETN expt 4
         RETN expt 8
        RETN expt 16
        ;Evaluation took 0 mSec (0 in gc) 613 cells work, 2299 env, 464 bytes other
        16
        ==>

        ==> (define (f x n) (if (= n 0) 1 (* x (g x (- n 1)))))
        ==> (define (g x n) (if (= n 0) 1 (+ x (f x (- n 1)))))
        ==> (trace f)
        ==> (trace g)
        CALL f 2 5
         CALL g 2 4
          CALL f 2 3
           CALL g 2 2
            CALL f 2 1
             CALL g 2 0
             RETN g 1
            RETN f 2
           RETN g 4
          RETN f 8
         RETN g 10
        RETN f 20
        ;Evaluation took 0 mSec (0 in gc) 423 cells work, 2005 env, 784 bytes other
        20
        ==>

[Prev]    [ Up ]    [Next]