あどけない話

インターネットに関する技術的な話など

再帰ドリル(1):数値に対する素朴な再帰

注意: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