Skip to content

Latest commit

 

History

History
198 lines (149 loc) · 5.61 KB

2.md

File metadata and controls

198 lines (149 loc) · 5.61 KB

再帰ドリル(2)：自然数に対する末尾再帰

等差数列の和

差が1の等差数列の和を素朴な再帰で実現すると以下のようになった。

my_soap :: Integer -> Integer
my_soap 0 = 0
my_soap n = my_soap (n-1) + n

プログラミング言語の内部をよく知っている人は、何度も関数を呼び出すのでスタックが溢れてしまわないか心配だろう。実際、この手の関数はスタックが溢れてしまう可能性がある。

そもそも、この程度の計算はループで実現できるはずで、スタックは溢れて欲しくはない。幸いにも、素朴な再帰を「末尾再帰」(tail recursion)という形に直すと、スタックが溢れなくなる。

末尾再帰の形をした関数とは、分岐の末端の最後で自分自身を呼び出す関数のことである。上記の関数は末尾再帰ではない。以下のように二項演算子を関数に直して前に出すと、よく分かる。

my_soap :: Integer -> Integer
my_soap 0 = 0
my_soap n = (+) (my_soap (n-1)) n

soap が最後に呼び出すのは、(+) であるから末尾再帰ではない。幸い、ループできることを実装している再帰関数は、「引数を増やすことで末尾再帰に直せる」。

my_soap_iter :: Integer -> Integer
my_soap_iter x = my_soap_iter' x 0

my_soap_iter' :: Integer -> Integer -> Integer
my_soap_iter' 0 acc = acc
my_soap_iter' n acc = my_soap_iter' (n-1) (acc + n)

作るべき関数の型は Integer -> Integer であるが、末尾再帰にするためには、一つ引数が増えて型が変わる。関数を二つ用意することで、この問題を解決している。

増やされた引数は「蓄積変数」(accumulator)と呼ばれる。上記の例では my_soap_iter' の acc がそれにあたる。蓄積変数に結果を蓄えていき、最後にそれを返す訳だ。

以下に、my_soap_iter 4 のときの my_soap_iter' の動きを示す。

  my_soap_iter'      4        0
= my_soap_iter' (4 - 1) (0 + 4)
= my_soap_iter'      3        4
= my_soap_iter' (3 - 1) (4 + 3)
= my_soap_iter'      2        7
= my_soap_iter' (2 - 1) (7 + 2)
= my_soap_iter'      1        9
= my_soap_iter' (1 - 1) (9 + 1)
= my_soap_iter'       0     10
= 10

my_soap との動きの違いを比べてみよう。

  my_soap 4
= my_soap (4 - 1) + 4
= my_soap 3 + 4
= (my_soap (3 - 1) + 3) + 4
= (my_soap 2 + 3) + 4
= ((my_soap (2 - 1) + 2) + 3) + 4
= ((my_soap 1 + 2) + 3) + 4
= (((my_soap (1 - 1) + 1) + 2) + 3) + 4
= (((my_soap 0 + 1) + 2) + 3) + 4
= (((0 + 1) + 2) + 3) + 4
= ((1 + 2) + 3) + 4
= (3 + 3) + 4
= 6 + 4
= 10

このドリルでは、トップレベルの関数が増えることを避けるために、末尾再帰のためのローカル関数を使う。ローカル関数の名前は iter とする。

my_soap_iter :: Integer -> Integer
my_soap_iter x = iter x 0
  where
    iter :: Integer -> Integer -> Integer
    iter 0 acc = acc
    iter n acc = iter (n-1) (acc + n)

変換の様式をまとめよう：

  • 蓄積変数を一つ増やす
  • 蓄積変数の初期値は、オリジナルの基底部が返す値にする
  • iter の基底部では蓄積変数を返す
  • iter の再帰部では蓄積変数に対して仕事をする

関数型言語を名乗るプログラミング言語であれば、末尾呼び出しは、単なるジャンプ(goto)に置き換えられるので、スタックは溢れない。(まぁ、この辺りが微妙な関数型言語もあるけれど。) これを「末尾呼び出しの最適化」(TCO: tail call optimization)と言う。

階乗

階乗を素朴な再帰で実現した

my_fact :: Integer -> Integer
my_fact 1 = 1
my_fact n = my_fact (n - 1) * n

は、以下のように変形できる。

my_fact_iter :: Integer -> Integer
my_fact_iter x = iter x 1
  where
    iter :: Integer -> Integer -> Integer
    iter 1 acc = acc
    iter n acc = iter (n - 1) (acc * n)

掛け算

掛け算を素朴な再帰で実現した

my_mul :: Integer -> Integer -> Integer
my_mul m 1 = m
my_mul m n = my_mul m (n - 1) + m

は、以下のように変形できる。

my_mul_iter :: Integer -> Integer -> Integer
my_mul_iter x y = iter x y x
  where
    iter :: Integer -> Integer -> Integer -> Integer
    iter _ 1 acc = acc
    iter m n acc = iter m (n - 1) (acc + m)

蓄積変数の初期値に注意。

演習

様式が分かったところで、演習に移ろう。

足し算

my_plus :: Integer -> Integer -> Integer
my_plus m 0 = m
my_plus m n = plus m (n - 1) + 1

これを末尾再帰の形に直せ。

my_plus_iter :: Integer -> Integer -> Integer
my_plus_iter x y = iter x y undefined
  where
    iter :: Integer -> Integer -> Integer -> Integer
    iter = undefined

引き算

my_minus :: Integer -> Integer -> Integer
my_minus m 0 = m
my_minus m n = minus m (n - 1) - 1

これを末尾再帰の形に直せ。

my_minus_iter :: Integer -> Integer -> Integer
my_minus_iter x y = iter x y undefined
  where
    iter :: Integer -> Integer -> Integer -> Integer
    iter = undefined

冪乗

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

これを末尾再帰の形に直せ。

my_power_iter :: Integer -> Integer -> Integer
my_power_iter x y = iter x y undefined
  where
    iter :: Integer -> Integer -> Integer -> Integer
    iter = undefined

[目次] [演習2]