情報システム科学実習 II (3)

再帰によるくり返し

1999 年 10 月 27 日増原英彦

補足事項:

• (第 2 回レジュメ B.1) ファイル~/.emacs に書くべき内容を以下のように修正:

          (setq scheme-program-name "\underline{/home/masuhara/lib/stk/bin/}stk")
   • 作ったボタンなどの消し方:(define b (make <Button> :text "Hello")) のよう

にして作ったボタンは(destroy b) のようにして消すことができる。 STk ウィンドウ

     中の全ての部品を消すには(for-each destroy (children *top-root*)) とする。

これは、トップレベルウィンドウに含まれる全ての部品に対してdestroy という関数を適用するという意味である。

• デバッグ方法。

• レポートの締切。

1 帰納的定義と再帰

「何かを繰り返して計算したい」ということは多い。 C のような手続き的プログラミングでは while や for のようなループによって書くことが多かったのだが、関数の中から自分自身を呼び出す再帰 (recursion) によって計算する。

例として、 1 + 2 + ⋯ + n を求める関数を定義してみよう。この関数を sum(n) と書くことにすると、次のように帰納的に定義できる。

sum(n) = \{ \begin{matrix}1 & n = 1 のとき \\ n + sum(n − 1) & それ以外 \end{matrix}

この定義の中では sum 自身を使っていることに注意。これは、ほとんどそのまま Scheme の定義に置き換えることができる:

       (define (sum n)
         (if (= n 1)
             1                         ; n が 1 のとき
             (+ n (sum (- n 1)))))     ; それ以外

練習 3-1: (再帰)

次の計算をする関数を定義せよ。

1. n の階乗 (n! = 1 × 2 × ⋯ × n) の帰納的な定義と Scheme の関数 (factorial n)

2. 「1 から n までの中にある m の倍数の個数」を求める Scheme の関数(count-multiples n m) を定義せよ。この関数を f(n, m) とすると、帰納的には次のように定義できる。

f(n, m) = \{ \begin{matrix}0 & n = 0 の場合 \\ 1 + f(n − 1, m) & n が m の倍数の場合 \\ f(n − 1, m) & それ以外 \end{matrix}

3. ある文字がある文字列の中に中回出現しているかを数える Scheme の関数

(count-characters-in-string str char) を定義せよ。 (ヒント: (string-length

s) は文字列 s の長さを計算する。 (string-ref s i) は文字列 s の i 番目の文字を計算する。 )

4. 積分の台形公式は

∫_{a}^{b} f(x)dx = (\frac{1}{2}f(a) + f(a + Δ) + f(a + 2Δ) + ⋯ + f(a + (n − 1)Δ) + \frac{1}{2}f(b)) Δ

(ただし Δ = (b − a)/n) である。これを用いて、 ∫_{a}^{b} sin xdx を求める(integral-sin a b n) を定義し、 ∫_{0}^{π} sin xdx を求めよ。

課題 3-1: (素数)

ある数 n が 2, 3, …, n − 1 のどれによっても割り切れない場合、 n は素数である。 n が素数であるかどうかを判定する関数を以下の順に定義せよ。

1. ある数 n がある数 m で割り切れる場合に真、そうでない場合に偽となる (divisible?

n m)。

2. n が l 以上 n 未満の整数でどれかで割り切れる場合に真、そうでない場合に偽となる (exists-divisor-from? n l)。この関数を f(n, l) とすると、次のように定義できる:

f(n, l) = \{ \begin{matrix}偽 & l ≥ n の場合 \\ 真 & n が l の倍数の場合 \\ f(n, l + 1) & それ以外 \end{matrix}

(この定義は工夫すれば cond や if を用いずにand やor を用いて作れる。 )

3. n が素数であるとは n が 2 以上 n 未満のいずれの整数でも割り切れない場合である。

(prime? n) をexists-divisor-from?を利用して定義せよ。

2 再帰の応用: ニュートン法

ニュートン法は、 (細い話は省略するが) 方程式 f(x) = 0 の解を数値的に求める方法で、

x_{0} = 適当な初期値
x_{i+1} = f′(x_{i})(x − x_{i}) + f(x_{i})

のようにして、 x_{i} を求めてゆき、 f(x_{i}) が充分 0 に近くなったところを近似解とするものである。

例えば、 n の平方根を求めたかったら、 f(x) = x^{2} − n, x_{0} = 1 とすればよいので

x_{0} = 1
x_{i+1} = \frac{1}{2} (x_{i} + \frac{n}{x_{i}} )

とすればよい。これを Scheme で書くと、

       (define (sqrt-iter x n)
         (if (good-enough? x n)
             x
             (sqrt-iter (improve x n) n)))

のようになる。 (good-enough? x n) は、 x^{2} ≃ n であるかを判定する関数である。ここでは |x^{2} − n| < δ で近似を終了することにして、

       (define delta 0.00001)
       (define (good-enough? x n)
         (< (abs (- (square x) n)) delta))

と書ける。また、 (improve x n) は、 x_{i} と n から x_{i+1} を求める関数で、

       (define (improve x n)
         (average x (/ n x)))

ただし、 average は二数の平均をとる関数で、

       (define (average x y)
         (/ (+ x y) 2))

である。最終的に、平方根を求める関数は x_{0} = 1 で始めることにしたので、

       (define (sqrt n)
         (sqrt-iter 1.0 n))

となる。

3 くり返し

くり返し的な処理も関数の再帰呼び出しによって定義できる。この場合、次のような構造になることが多い。

  (define (くり返し処理パラメータ...)

(if 処理を続けるか?

        (begin

処理の中身 ⋮

(くり返し処理 (次のくり返しのパラメータを計算)))))

例として、「タートルグラフィクス」によって絵を描いてみよう。タートルグラフィクスでは、陸亀に対して「何歩進め」 (walk) と「曲がれ」 (turn) という指示が出せる。

(load "turtle.scm") ; web ページによって提供

;; タートルグラフィクスの領域を作り

(define gamera (make <Turtle> :width 300 :height 300))

;; 表示する

(pack gamera)
(walk gamera 50)                ; 50 歩進め!
(turn gamera 45)                ; 45 度まわれ!
(jump gamera 100)               ; 100 歩飛べ!
;; (reset gamera)               ; 画面を消して元に戻す

これを使って一辺の長さが l の正 n 角形を描くには、以下のように繰り返しをすればよい (web ページに定義あり):

;; regular-polygon.scm
;; count 個の辺を描く
(define (polygon-side turtle count side-length delta-angle)
  (if (< 0 count)
      (begin
        (walk turtle side-length)
        (turn turtle delta-angle)
        (update)                        ; 画面を更新
        (polygon-side turtle (- count 1)
                      side-length delta-angle))))
;; 正 num-edges 角形を描く
(define (regular-polygon turtle num-edges side-length)
  (polygon-side turtle num-edges side-length (/ 360 num-edges)))

4 複雑な再帰

ここまで見た再帰呼び出しでは、 1 つの関数からその関数を 1 回だけ呼びしている。もっと複雑な再帰も同様に扱える。

例として木を描く関数を定義してみよう。ここでは、幹を描いたあと、次の段階の枝を 2 つ描くために自分自身を 2 回呼び出している。 (Web ページに定義あり。 )

;; tree.scm             (turtle.scm を使用)
(define minimum-branch-length 5) ; 最小の枝の長さ
;; 枝の長さ length, 枝の縮少率を length-factor,

;; 分岐の角度を angle として木を描く

(define (tree turtle length length-factor angle)
(update)

;; 枝が充分長ければ計算を続ける

(if (< minimum-branch-length length)
(let ((new-length (* length-factor length))); 次の枝長
(walk turtle length)                     ; 幹を描く
(turn turtle angle)
(tree turtle new-length length-factor angle); 次の枝 1
(turn turtle (* -2 angle))
(tree turtle new-length length-factor angle); 次の枝 2
(turn turtle angle)
(jump turtle (- length)))))         ; 元の位置に戻る

課題 3-2: (フィボナッチ数)

フィボナッチ数列 (Fibonacci numbers) とは、

0, 1, 1, 2, 3, 5, 8, 13, 21, …

のように、「前 2 つの数の和」で作られる数の列である。 n 番目のフィボナッチ数 fib(n) を帰納的に定義せよ。また、 Scheme 関数(fibonacci n) を定義せよ。

課題 3-3: (タートルグラフィックス)

タートルグラフィックスライブラリを利用して、絵を描く関数を定義せよ。ただし、再帰を用いること。

5 おまけ: 関数のブラックボックス化:

• 問題を小問題に分割→それぞれに関数定義

• 小問題はそれぞれブラックボックスとして扱える

• 細かな関数定義が沢山できしてしまう

→局所的な定義によるブロック構造化

(define (sqrt n)
(define delta 0.00001)
(define (good-enough? x n)
(< (abs (- (square x) n)) delta))
(define (improve x n)
(average x (/ n x)))
(define (sqrt-iter x n)
(if (good-enough? x n)
   x
   (sqrt-iter (improve x n) n)))
(sqrt-iter 1.0 n))

• 名前の見える範囲 (スコープ)

ある関数定義の内側で定義されている名前は、その関数定義の中だけしか見えない。上のようなブロック化をした場合は、 delta, good-enough?等の名前は sqrt の定義の内側でしか使えない。

一方、関数の内側で定義している関数には、その外側の名前が見えている。例えば、 improve の定義内部では、 sqrt への引数 n が見えている。そのため、上の定義はもっと簡略化できて、次のようにもできる。

     (define (sqrt n)
       (define delta 0.00001)
       (define (good-enough? x)
         (< (abs (- (square x) n)) delta))
       (define (improve x)
         (average x (/ n x)))
       (define (sqrt-iter x)
         (if (good-enough? x)
             x
             (sqrt-iter (improve x))))
       (sqrt-iter 1.0))