注意:github に移動しました。
再帰を学ぶためのドリル。使用するプログラミング言語は Haskell。このシリーズは続くかもしれないし、途中で挫折するかもしれない。乞うご期待!
等差数列の和
差が1の等差数列の和を計算する関数 soap(sum of arithmetic progression) を考える。
soap 0 = 0 soap 1 = 0 + 1 soap 2 = 0 + 1 + 2 soap 3 = 0 + 1 + 2 + 3 soap 4 = 0 + 1 + 2 + 3 + 4
一歩手前を使うとどうなる?
soap 0 = 0 soap 1 = soap 0 + 1 soap 2 = soap 1 + 2 soap 3 = soap 2 + 3 soap 4 = soap 3 + 4
再帰部を一般化するとどうなる?
soap 0 = 0 -- 基底部 soap n = soap (n-1) + n -- 再帰部
階乗
階乗を計算する関数 fact を考える。
fact 1 = 1 fact 2 = 1 * 2 fact 3 = 1 * 2 * 3 fact 4 = 1 * 2 * 3 * 4 fact 5 = 1 * 2 * 3 * 4 * 5
一歩手前を使うとどうなる?
fact 1 = 1 fact 2 = fact 1 * 2 fact 3 = fact 2 * 3 fact 4 = fact 3 * 4 fact 5 = fact 4 * 5
再帰部を一般化するとどうなる?
fact 1 = 1 fact n = fact (n - 1) * n
掛け算
掛け算する関数 mul を考える。
mul m 1 = m mul m 2 = m + m mul m 3 = m + m + m mul m 4 = m + m + m + m mul m 5 = m + m + m + m + m
一歩手前を使うとどうなる?
mul m 1 = m mul m 2 = mul m 1 + m mul m 3 = mul m 2 + m mul m 4 = mul m 3 + m mul m 5 = mul m 4 + m
再帰部を一般化するとどうなる?
mul m 1 = m mul m n = mul m (n - 1) + m
演習
以下の関数に対して、再帰の定義を考えなさい。
plus m 0 = m plus m 1 = m + 1 plus m 2 = m + 1 + 1 plus m 3 = m + 1 + 1 + 1 plus m 4 = m + 1 + 1 + 1 + 1
minus m 0 = m minus m 1 = m - 1 minus m 2 = m - 1 - 1 minus m 3 = m - 1 - 1 - 1 minus m 4 = m - 1 - 1 - 1 - 1
power m 1 = m power m 2 = m * m power m 3 = m * m * m power m 4 = m * m * m * m power m 5 = m * m * m * m * m