再帰プログラミング

言語

再帰プログラミング

◇ 1. これはリストの中にあるか

　どんなに複雑なリストでも、そのなかに探しているアトムが有るかどうかを判定する関数を作ってみる。
　探すアトムをa、リストをsという仮引数にして、"Is a in s?" にちなんで関数の名前を isin にしてみる。　　　　　　　　　　

　　1-1. 素朴な方針

　未知のリストsが空だったらnilを返す
　car部がアトムだったら、a と一致するかどうか判断し、真だったらtを返し、偽だったら残りのcdr部を調べる
　car部がアトムでなかったら、すなわちリストだったら、それをcar部とcdr部に分けてさらに深く調べる。

　このような方針でプログラムを作ると次のように考えがまとまっていく。
なお、(consp s) は (and (listp s) (not (atom s))) と同じである。




        (defun isin (a s)

          (cond ((null s) nil)

                ((atom (car s)) (if (equal a (car s))

                                  t

                                  (isin a (cdr s))))

                ((consp (car s)) (or (isin a (car s))

                                     (isin a (cdr s))))))





        (defun isin (a s)

          (cond ((null s) nil)

                ((atom (car s)) (if (equal a (car s))

                                  t

                                  (isin a (cdr s))))

                (t (or (isin a (car s)) (isin a (cdr s))))))





        (defun isin (a s)

          (cond ((null s) nil)

                ((atom (car s)) (or (equal a (car s))

                                    (isin a (cdr s))))

                (t (or (isin a (car s)) (isin a (cdr s))))))





        (defun isin (a s)

          (cond ((null s) nil)

                ((and (atom (car s)) (equal a (car s))) t)

                ((atom (car s)) (isin a (cdr s)))

                (t (or (isin a (car s)) (isin a (cdr s))))))

　ここで、(setq x '(a b (1 c 2 (d e)) (f (3 (g 4) 5) h) 6)) として (isin 'a x)を評価すればｔが返り、(isin 'k x)を評価すればnilが返ってくるわけである。

　この方針でのisin関数は、最終的に次のように整理できます。




      (defun isin (a s)

        (cond ((null s) nil) ;空リストである

              ((equal a (car s)) t) ;アトムだとしたら一致しているか

              ((atom (car s)) (isin a (cdr s))) ;アトムだったが一致しなかった

              (t (or (isin a (car s)) (isin a (cdr s)))))) ;アトムでなかった

1-2. リストを2進木と考え、木の枝をたどって全て葉にまで達したところで考える

　未知のリストsに枝がなかったらnilを返す。
　なお、枝はリスト構造を示し、葉はアトムを示すものとする。




    (defun isin (a s)

       (cond ((null s) nil)

             ((atom s) (if (equal a s)

                         t

                         nil))

             ((consp s) (or (isin a (car s))

                            (isin a (cdr s))))))





    (defun isin (a s)

       (cond ((null s) nil)

             ((atom s) (if (equal a s)

                         t

                         nil))

             (t (or (isin a (car s)) (isin a (cdr s))))))





　　nilと()は同じものである。

　

    (defun isin (a s)

       (cond ((null s) nil) ;nilはアトムである。そして()は空リストである。

             ((atom s) (equal a s))

             (t (or (isin a (car s)) (isin a (cdr s))))))



　



    (defun isin (a s)

       (cond ((atom s) (equal a s)) ;空リストの場合もここで判断できる。

             (t (or (isin a (car s)) (isin a (cdr s))))))

1-3. あまり本質的ではないが、アトムよりも先にリストを調べる方法も考えられる


　(i) car部を先読みする場合



     (defun isin (a s)

        (cond ((null s) nil)

              ((consp (car s)) (or (isin a (car s))

                                   (isin a (cdr s))))

              ((atom (car s)) (if (equal a (car s))

                                t

                                (isin a (cdr s))))))





     (defun isin (a s)

        (cond ((null s) nil)

              ((consp (car s)) (or (isin a (car s))

                                   (isin a (cdr s))))

              (t (if (equal a (car s))

                   t

                   (isin a (cdr s))))))





     (defun isin (a s)

        (cond ((null s) nil)

              ((consp (car s)) (or (isin a (car s))

                                   (isin a (cdr s))))

              ((equal a (car s) t)

              (t (isin a (cdr s))))))







　(ii) 葉のレベルまで達してから調べる場合



     (defun isin (a s)

        (cond ((null s) nil)

              ((consp (car s)) (or (isin a (car s))

                                   (isin a (cdr s))))

              ((atom s) (equal a s))))





     (defun isin (a s)

        (cond ((null s) nil)

              ((consp (car s)) (or (isin a (car s))

                                   (isin a (cdr s))))

              (t (equal a s))))

◇ 2. 数だけを要素とするリスト

　文字と数の混じった複雑なリストから数だけを残して単純なリストにするプログラムを作ってみる。

　文字と数の混じったリストを表す仮引数をsとし、関数の名前をnumbersとする。　　　　　　　　　　

2-1. 素朴な方針

　car部がアトムだったら、数かどうかを判断し、真だったらそのリストの頭に入れ、偽だったら残りのcdr部を調べる。
　car部がアトムでなかったら、すなわちリストだったら、それをcar部とcdr部に分けてさらに深く調べる。
　car部とcdr部に分けて調べたものはリストになるのでappendで接続する。

　このような方針でプログラムを作ると次のように考えがまとまっていく。




   (defun numbers (s)

     (cond ((null s) nil)

           ((atom (car s)) (if (numberp (car s))

                             (cons (car s) (numbers (cdr s)))

                             (numbers (cdr s))))

           ((consp (car s)) (append (numbers (car s))

                                    (numbers (cdr s))))))





  (defun numbers (s)

     (cond ((null s) nil)

           ((and (atom (car s)) (numberp (car s)))

                                (cons (car s) (numbers (cdr s))))

           ((atom (car s)) (numbers (cdr s)))

           ((consp (car s)) (append (numbers (car s))

                                    (numbers (cdr s))))))





  (defun numbers (s)

     (cond ((null s) nil)

           ((and (atom (car s)) (numberp (car s)))

                                (cons (car s) (numbers (cdr s))))

           ((atom (car s)) (numbers (cdr s)))

           (t (append (numbers (car s)) (numbers (cdr s))))))

　ここで、(setq x '(a b (1 c 2 (d e)) (f (3 (g 4) 5) h) 6)) として (numbers x)を評価すれば(1 2 3 4 5)というリストが返ってくる。

　この方針でのnumbers関数は、最終的に次のように整理できます。




  (defun numbers (s)

     (cond ((null s) nil)

           ((numberp (car s)) (cons (car s) (numbers (cdr s))))

           ((atom (car s)) (numbers (cdr s)))

           (t (append (numbers (car s)) (numbers (cdr s))))))

2-2. リストを2進木と考え、木の枝をたどって全て葉にまで達したところで考える

　未知のリストsに枝がなかったらnilを返す。
　なお、枝はリスト構造を示し、葉はアトムを示すものとする。




  (defun numbers (s)

     (cond ((null s) nil)

           ((atom s) (if (numberp s)

                       (list s)

                       nil))

           ((consp s) (append (numbers (car s))

                              (numbers (cdr s))))))





  (defun numbers (s)

     (cond ((null s) nil)

           ((atom s) (if (numberp s) (list s)))

           ((consp s) (append (numbers (car s))

                              (numbers (cdr s))))))





  (defun numbers (s)

     (cond ((atom s) (if (numberp s) (list s)))

           (t (append (numbers (car s)) (numbers (cdr s))))))



             

  (defun numbers (s)

     (cond ((numberp s) (list s))

           ((atom s) nil) 

           (t (append (numbers (car s)) (numbers (cdr s))))))

2-3. あまり本質的ではないが、アトムよりも先にリストを調べる方法も考えられる


　(i) car部を先読みする場合



  (defun numbers (s)

     (cond ((null s) nil)

           ((consp (car s)) (append (numbers (car s))

                                    (numbers (cdr s))))

           ((atom (car s)) (if (numberp (car s))

                             (cons (car s) (numbers (cdr s)))

                             (numbers (cdr s))))))





  (defun numbers (s)

     (cond ((null s) nil)

           ((consp (car s)) (append (numbers (car s))

                                    (numbers (cdr s))))

           ((and (atom (car s)) (numberp (car s)))

                                (cons (car s) (numbers (cdr s))))

           ((atom (car s)) (numbers (cdr s)))))





  (defun numbers (s)

     (cond ((null s) nil)

           ((consp (car s)) (append (numbers (car s))

                                    (numbers (cdr s))))

           ((numberp (car s)) (cons (car s) (numbers (cdr s))))

           ((atom (car s)) (numbers (cdr s)))))





　(ii) 葉のレベルまで達してから調べる場合



  (defun numbers (s)

     (cond ((null s) nil)

           ((consp s) (append (numbers (car s)) (numbers (cdr s))))

           ((atom s) (if (numberp s) (list s) nil))))

                                    ;then    ;else



  (defun numbers (s)

     (cond ((null s) nil)

           ((consp s) (append (numbers (car s)) (numbers (cdr s))))

           ((atom s) (if (numberp s) (list s))))) 





  (defun numbers (s)

     (cond ((null s) nil)

           ((consp s) (append (numbers (car s)) (numbers (cdr s))))

           (t (if (numberp s) (list s))))) 





  (defun numbers (s)

     (cond ((null s) nil)

           ((consp s) (append (numbers (car s)) (numbers (cdr s))))

           ((numberp s) (list s))))

言語

言語の目次へ戻る