Skip to content

Latest commit

 

History

History
173 lines (123 loc) · 5.86 KB

5.md

File metadata and controls

173 lines (123 loc) · 5.86 KB

再帰ドリル(5)：自然数に対する少し複雑な再帰

今回学ぶ再帰は少し複雑だが、すべてループと同等である。

最大公約数

最大公約数(GCD: greatest common divisor)は、中学校で習っただろう。そのアルゴリズムの要は、共通因数を見つけることである。共通因数を見つけるには、素因数分解しないといけない。素因数分解のためには、素数表を作成する必要がある。大きな数が素数であるか判定するのは、かなり難しいし時間がかかる。よって、このアルゴリズムは現実的ではない。

最大公約数を算出するには、実はとても簡単な方法がある。なぜ中学校でこちらを教えないか不思議なくらいだ。2 以上の自然数 a と b があって、a >= b とすると、最大公約数は、a - b で計算できる。ウソだと思うかもしれないので、実際に試してみよう。12 と 8 の最大公約数は 4 である。12 から 8 を引くと 4 になるから、見事に最大公約数が求まっている。

その種明かしをしよう。a と b の最大公約数を G とし、a = G * A、b = G * B とおく。a - b = G (A - B) なので、引き算しても G は消えない。A - B の部分を 1 にできれば、G が求まるというわけだ。これを再帰で実装すると以下のようになる。

my_gcd :: Integer -> Integer -> Integer
my_gcd a 0 = a
my_gcd a b
  | c >= b    = my_gcd c b
  | otherwise = my_gcd b c
  where
    c = a - b

my_gcd は a >= b と仮定していることに注意。なぜ基底部がこうなるのかは自分で考えること。

演習

my_gcd は何度も引き算をして、c >= b のときにはじめて引数をひっくり返した。何度も引いて、最後に小さくなるものとは、余りに他ならない。よって、余りを計算するようにすれば、この関数は劇的に速くなる。

Haskell で整数の割り算をする関数は div、余りを計算する関数は mod である。mod を使って、my_gcd を書き直し、my_gcd_fast として定義せよ。

my_gcd_fast :: Integer -> Integer -> Integer
my_gcd_fast = undefined

正しく実装できていれば、引数の順番も任意でよくなっている。これはなぜか？

演習

最小公倍数(LCM: least common multiple) を求める関数 my_lcm_fast を my_gcd_fast を使って実装せよ。

my_lcm_fast :: Integer -> Integer -> Integer
my_lcm_fast = undefined

ヒント：これは再帰を使わない。

冪乗

冪乗を計算する関数 power を思い出そう。

my_power :: Integer -> Integer -> Integer
my_power _ 0 = 1
my_power m n = my_power m (n - 1) * m

演習

実は冪乗をさらに高速に計算するアルゴリズムが存在する。指数が 2 の冪乗であれば、倍、倍、倍、と計算していけることを利用する。たとえば、2^11 を考えよう、これは 2^1 * 2^2 * 2^8 である。よって、ビットが立っていれば、そのときの m^x (ただし x は 2 の冪乗)を掛ければよい。

以下の undefined の部分を書き換えて、高速な冪乗計算を実装せよ。

my_power_fast :: Integer -> Integer -> Integer
my_power_fast _ 0 = 1
my_power_fast m n
  | odd n     = my_power_fast undefined undefined * m
  | otherwise = my_power_fast undefined undefined

ヒント：n を 2 進数表記で表した場合、odd は最も右の桁のビットが立っているかを調べている。

演習

冪乗の末尾再帰版 my_power_iter を思い出そう。

my_power_iter :: Integer -> Integer -> Integer
my_power_iter x y = iter x y 1
  where
    iter :: Integer -> Integer -> Integer -> Integer
    iter _ 0 acc = acc
    iter m n acc = iter m (n - 1) (acc * m)

この実装に対しても高速版を実装せよ。

my_power_fast_iter :: Integer -> Integer -> Integer
my_power_fast_iter x y = iter x y 1
  where
    iter :: Integer -> Integer -> Integer -> Integer
    iter _ 0 acc = acc
    iter m n acc
      | odd n     = iter undefined undefined undefined
      | otherwise = iter undefined undefined undefined

フィボナッチ数列

Haskell では、フィボナッチ数列をあたかも数学の定義のように実装できる。

my_fib :: Integer -> Integer
my_fib 0 = 0
my_fib 1 = 1
my_fib n = my_fib (n - 2) + my_fib (n - 1)

このように、自分自身を複数回呼び出す再帰を「多重再帰」という。

演習

my_fib の末尾再帰版 my_fib_iter を実装せよ。

my_fib_iter :: Integer -> Integer
my_fib_iter a = iter a 0 1
  where
    iter :: Integer -> Integer -> Integer -> Integer
    iter 0 x _ = x
    iter n x y = iter undefined undefined undefined

蓄積変数が2つあることに注意。

偶数奇数

偶数か奇数かを調べる関数 my_even と my_odd を思い出そう。

my_even :: Integer -> Bool
my_even 0 = True
my_even 1 = False
my_even n = my_even (n - 2)

my_odd :: Integer -> Bool
my_odd 0 = False
my_odd 1 = True
my_odd n = my_odd (n - 2)

これは、以下のように互いに呼び合うように変更できる。

my_even_m :: Integer -> Bool
my_even_m 0 = True
my_even_m n = my_odd_m (n - 1)

my_odd_m :: Integer -> Bool
my_odd_m 0 = False
my_odd_m n = my_even_m (n - 1)

このような再帰を「相互再帰」という。相互再帰は、後で学ぶ「リストに対する再帰」で驚くべき力を発揮する。

演習

my_odd_m の基底部も True を返すよう実装できるだろうか？

my_even_m2 :: Integer -> Bool
my_even_m2 0 = True
my_even_m2 n = undefined

my_odd_m2 :: Integer -> Bool
my_odd_m2 1 = True
my_odd_m2 n = undefined

[目次] [演習5]