Parenist養成ゼミ: 再帰

この記事は、Parenist養成ゼミシリーズの記事である。

今回は、lisperの基本的な思考方法である再帰の理解を目的とした。

リスト、制御構造、再帰と講義を終えたので、多少lisperの思考回路が形成されて来たのではないだろうか。

rec.p

recursion

前回までの講義で、関数を用いると複数の式をまとめて抽象化できることを学んだ。

それらの式には、任意の関数の呼び出しを記述することができ、それには自分自身も含まれる。

自分自身を呼び出す関数は再帰的（recursive）と呼ばれる。

listがcons cellによる再帰的な構造であることと、empty listを偽として定義している事があいまって、Parenではlistを操作する関数を再帰で簡潔に記述できる。

例えば、listの要素数を返す関数lengthを考えてみる。手続き的には以下のように書ける。

(function length (lis)
  (let (n 0)
    (dolist (i lis)
      (<- n (++ n)))
    n))

これは、再帰的に以下のように書き直すことができる。

(function length (lis)
  (if lis (++ (length (cdr lis)))
      0))

再帰的関数を定義するとき、考えるべき事は以下の二つである。

base case

2. recursive case

base case

再帰に依らない普遍的な条件をbase caseという。

先の例では、empty listを0と定義している部分がそれにあたる。

base caseは単純であることが多いため、先頭に記述すると見通しがよい事が多い。

(function length (lis)
  (if (nil? lis) 0
      (++ (length (cdr lis)))))

recursive case

再帰関数の再帰的な部分をrecursive caseという。

recursive caseを有限回繰り返すとbase caseに遷移するように設計する。

先の例では、あるlistの長さは、1 + （自分自身よりも長さが1短いlistの長さ）と記述することにより有限回のstepでbase caseに収束するように定義されている。

課題

付録のrec.pを作成し、main関数を変更することなしにpassが表示されるようにプログラムを修正せよ。

実行例

$ paren rec.p
pass

付録

rec.p

; recursion.

(function x^y (x y)
  '?)

(function n! (n)
  '?)

(function nCr (n r)
  '?)

(function fib (n)
  '?)

(function take (lis n)
  '?)

(function drop (lis n)
  '?)

(function get-last (lis)
  '?)

(function append-last (lis x)
  '?)

(function remove-last (lis)
  '?)

(function _reverse (lis)
  '?)

(function rotate (lis)
  '?)

(function count-nil (lis)
  '?)

(function replace (lis from to)
  '?)

(macro test (x y)
  `(if (!= ,x ,y) (raise Error (str "assert failed " (list :expr ',x :evaluated ,x :expected ',y)))))

(function! main (args)
  (test (map (f (y) (x^y 2 y)) (.. 5)) '(1 2 4 8 16))
  (test (map n! (map ++ (.. 5))) '(1 2 6 24 120))
  (test (list (nCr 0 0)) '(1))
  (test (list (nCr 1 0) (nCr 1 1)) '(1 1))
  (test (list (nCr 2 0) (nCr 2 1) (nCr 2 2)) '(1 2 1))
  (test (list (nCr 3 0) (nCr 3 1) (nCr 3 2) (nCr 3 3)) '(1 3 3 1))
  (test (map fib (map ++ (.. 6))) '(1 1 2 3 5 8))
  (test (take nil 2) nil)
  (test (take '(0) 2) '(0))
  (test (take (.. 3) 2) '(0 1))
  (test (drop nil 2) nil)
  (test (drop '(0) 2) nil)
  (test (drop (.. 3) 2) '(2))
  (test (get-last nil) nil)
  (test (get-last '(0)) 0)
  (test (get-last (.. 3)) 2)
  (test (append-last nil 0) '(0))
  (test (append-last '(0) 1) '(0 1))
  (test (append-last (.. 3) 3) (.. 4))
  (test (remove-last nil) nil)
  (test (remove-last '(0)) nil)
  (test (remove-last (.. 3)) (.. 2))
  (test (_reverse nil) nil)
  (test (_reverse '(0)) '(0))
  (test (_reverse (.. 3)) '(2 1 0))
  (test (rotate nil) nil)
  (test (rotate '(0)) '(0))
  (test (rotate '(0 1)) '(1 0))
  (test (rotate '(0 1 2)) '(2 0 1))
  (test (count-nil '(a () b)) 1)
  (test (count-nil '(a () b () c)) 2)
  (test (append-last '() 1) '(1))
  (test (append-last '(1 2 3) 4) '(1 2 3 4))
  (test (replace '(a () b) nil 'x) '(a x b))
  (test (replace '(a () b () c) 'a nil) '(() () b () c))
  (test (replace '(a () b () c) 'x nil) '(a () b () c))
  (write 'pass))