プログラミング言語 Standard ML 入門 (問題の解答例)

2.3 再帰的関数

問 2.2

factorial 関数が正しく動作することを， factorial 0， factorial 2， factorial 3 の各場合の動作をトレースすることによって確かめよ．

解答例 factorial 3の呼び出しは以下のようなトレースを生成する．

   factorial 3
    > 3 * factorial 2
    >      > 2 * factorial 1
    >      >      > 1 * factorial 0
    >      >      >      > 1
    >      >      > 1 * 1
    >      >      > 1
    >      > 2 * 1
    >      > 2
    > 3 * 2
    > 6

問 2.3

以下の各数列 $S_{n}$ について， $S_{n}$ が満たすべき性質を $n$ に関する漸化式として記述し，それに対応する再帰的関数を記述することによって， $S_{n}$ を求めるプログラムを書け．

1.

$S_{n}=1+2+\cdots+n$
2.

$S_{n}=1+(1+2)+(1+2+3)+\cdots+(1+2+\cdots+n)$

解答例

1.
漸化式は

$\displaystyle S_{0}$ $\displaystyle=$ $\displaystyle 0$

$\displaystyle S_{n}$ $\displaystyle=$ $\displaystyle n+S_{n-1}$

と与えられる．よって，この関数をfとすると，以下のコードで実現できる．
```
   fun f 0 = 0
     | f n = n + f (n - 1);
```
2.
漸化式は、上記の漸化式の解を $S_{n}$ として、

$\displaystyle T_{0}$ $\displaystyle=$ $\displaystyle 0$

$\displaystyle T_{n}$ $\displaystyle=$ $\displaystyle T_{n-1}+S_{n}$

と与えられる．よって，この関数をgとすると，以下のコードで実現できる．
```
   fun g 0 = 0
     | g n = g (n - 1) + f n;
```

問 2.4

問2.3で定義した2つの関数が，それぞれ正しく数列の和を計算することを，入力 $n$ に関する帰納法で証明せよ．

解答例

1.
$S_{n}=1+2+...+n$
1. (a)
  
  （基底）n = 0のとき． $S_{0}=0$ , $\mbox{\tt f 0}=\mbox{\tt 0}$ で正しい．
2. (b)
  
  （帰納段階）n = kのとき正しいと仮定する．
  
  $S_{k+1}=1+2+...+k+(k+1)=S_{k}+(k+1)$
  
  である．一方f (k + 1) = (k + 1) + f kであり，帰納法の仮定より $\mbox{\tt f k}=S_{k}$ であるから， $\mbox{\tt f (k + 1)}=S_{k+1}$ である．
2.
$S_{n}=1+(1+2)+(1+2+3)+...+(1+2+...+n)$
1. (a)
  
  （基底） $n=0$ のとき, $S_{0}=0$ , $\mbox{\tt f 0}=0$ で正しい．
2. (b)
  
  （帰納段階） $n=k$ のとき正しいと仮定する．
  
  $\displaystyle S_{k+1}$ $\displaystyle=$ $\displaystyle 1+(1+2)+(1+2+3)+...+(1+2+...+k)+(1+2+...+k+(k+1))$
  
  $\displaystyle=$ $\displaystyle S_{k}+(1+2+...+k+(k+1))$
  
  である．一方 $\mbox{\tt f (k + 1)}=\mbox{\tt f k + g (k + 1)}$ であり，帰納法の仮定と前項の結果より $\mbox{\tt f k}=S_{k}$ かつ $\mbox{\tt g (k+1)}=(1+2+...+k+(k+1))$ であるから， $\mbox{\tt f (k + 1)}=S_{k+1}$ である．

問 2.5

以下のように再帰的に定義される数列をフィボナッチ数列と呼ぶ．

$\displaystyle F_{0}$	$\displaystyle=$	$\displaystyle 0$
$\displaystyle F_{1}$	$\displaystyle=$	$\displaystyle 1$
$\displaystyle F_{n}$	$\displaystyle=$	$\displaystyle F_{n-2}+F_{n-1}\ \ \ \ \ (n\geq 2)$

負でない整数 $n$ を受け取り $F_{n}$ を計算する関数 fib を定義せよ．

解答例

   fun fib n = if n = 0 then 0
               else if n = 1 then 1
               else fib (n - 1) + fib (n - 2)

問 2.6

$k$ を与えられた負でない整数とし，任意の $0\leq n\leq k$ について fib n が $F_{n}$ を計算することを， $k$ に関する数学的帰納法で示せ．これを用いて，fib が，0以上の任意の自然数に対して正しく $F_{n}$ の値を計算することを確認せよ．

解答例任意の $0\leq n\leq k$ についてfib n が $F_{n}$ を計算することの $k$ に関する帰納法による証明

•

$k=0,1$ の時． $\mbox{\tt fib 0}=0=F_{0}$ かつ $\mbox{\tt fib 1}=1=F_{1}$ であり成立．
•

$k=i(i\geq 1)$ の時成立すると仮定する． $\mbox{\tt fib ($i$ + 1)}=\mbox{\tt fib $i$}+\mbox{\tt fib ($i$ - 1)}$ である．帰納法の仮定より， $\mbox{\tt fib $i$}=F_{i}$ かつ $\mbox{\tt fib ($i$ - 1)}=F_{i-1}$ である．また定義より， $F_{i}=F_{i-1}+F_{i-2}$ である．よって， $\mbox{\tt fib $i$}=F_{i}$ となる．従って，任意の $0\leq n\leq i+1$ について $\mbox{\tt fib n}=F_{n}$ であり，成立する．

以上より， $0$ 以上の任意の $k$ に対して，任意の $0\leq n\leq k$ について $\mbox{\tt fib n}=F_{n}$ であるから， $0$ 以上の任意の自然数に対して正しく $F_{n}$ の値を計算する．

問 2.7

フィボナッチ数列 $F_{n}$ の再帰的定義をそのまま再帰的関数として実現すると， $F_{n}$ の計算に掛かる時間は $n$ が大きくなるに従って指数関数的に増大する． $F_{n}$ を $n$ に比例する時間で計算する関数 fastFib を以下の洞察を参考に定義せよ．

1.

フィボナッチ数列の定義は，連続する2つの数から次の数を決めるような構成になっている．したがって， $F_{k}$ と $F_{k+1}$ が与えられれば $F_{k+2}$ が即座に求められる．この作業を $n-1$ 回繰り返せば， $F_{k}$ と $F_{k+1}$ から $F_{k+n}$ が求められるはずである．
2.

前項の考え方を参考に，与えられた連続する2つのフィボナッチ数 $F_{k}$ と $F_{k+1}$ から， $F_{k}$ の $n$ 個先のフィボナッチ数を求める関数 G( $n$ , $F_{k}$ , $F_{k+1}$ ) を定義する． $n$ が $0$ の場合は $F_{k}$ を返せばよい． $n$ が $1$ の場合は $F_{k+1}$ を返せばよい． $n$ が $2$ 以上の場合は， $F_{k}$ と $F_{k+1}$ から $F_{k+2}$ を求め， $F_{k+1}$ と $F_{k+2}$ から， $F_{k+1}$ の $n-1$ 個先のフィボナッチ数を求めればよいから，G( $n-1$ , $F_{k+1}$ , $F_{k}+F_{k+1}$ ) を呼び出せばよい．
3.

$F_{n}$ は $F_{0}$ から $n$ 個先のフィボナッチ数であるから，G(n, $F_{0}$ , $F_{1}$ ) である．したがって fastFib は，上記の動作をする補助関数 G を呼び出すことによって実現できる．

解答例

   fun G(n,fk,fk1) = if n = 0 then fk
                     else if n = 1 then fk1
                     else G(n-1,fk1,fk+fk1);
   fun fastFib n = G(n,0,1);

問 2.8

負でない任意の整数 $n$ に対してG( $n$ , $F_{k}$ , $F_{k+1}$ )は $F_{k+n}$ を計算することを， $n$ に関する数学的帰納法で証明せよ．この性質を使って，fastFib $n$ が正しくフィボナッチ数 $F_{n}$ を計算することを示せ．

解答例

•

$n=0,1$ の時。

G(0, $F_{k}$ , $F_{k+1}$ ) $\displaystyle=$ $\displaystyle F_{k}$

G(1, $F_{k}$ , $F_{k+1}$ ) $\displaystyle=$ $\displaystyle F_{k+1}$

であり成立する．
•

$n=i+1(i\geq 1)$ の時。 Gの定義より

$\mbox{\tt G($i+1$,$F_{k}$, $F_{k+1}$)}=\mbox{\tt G($i$, $F_{k+1}$, $F_{k}+F_{k% +1}$)}$

である． $F_{n}$ の定義より， $F_{k}+F_{k+1}=F_{k+2}$ である．よって， $\mbox{\tt G($i+1$, $F_{k}$, $F_{k+1}$)}=\mbox{\tt G($i$,$F_{k+1}$,$F_{k+2}$)}$ である．帰納法の仮定より， $\mbox{\tt G($i+1$,$F_{k}$,$F_{k+1}$)}=F_{k+i+1}$ となり成立する．

以上の特殊な場合として， $\mbox{\tt G($n$,$F_{0}$,$F_{1}$)}=F_{n}$ であり，したがって， $\mbox{\tt fastFib $n$}=F_{n}$ である．

	$\displaystyle S_{0}$	$\displaystyle=$	$\displaystyle 0$
	$\displaystyle S_{n}$	$\displaystyle=$	$\displaystyle n+S_{n-1}$

	$\displaystyle T_{0}$	$\displaystyle=$	$\displaystyle 0$
	$\displaystyle T_{n}$	$\displaystyle=$	$\displaystyle T_{n-1}+S_{n}$

	$\displaystyle S_{k+1}$	$\displaystyle=$	$\displaystyle 1+(1+2)+(1+2+3)+...+(1+2+...+k)+(1+2+...+k+(k+1))$
		$\displaystyle=$	$\displaystyle S_{k}+(1+2+...+k+(k+1))$

	G(0, $F_{k}$ , $F_{k+1}$ )	$\displaystyle=$	$\displaystyle F_{k}$
	G(1, $F_{k}$ , $F_{k+1}$ )	$\displaystyle=$	$\displaystyle F_{k+1}$