1.md

再帰ドリル(1)：自然数に対する素朴な再帰

再帰を学ぶためのドリル。

等差数列の和

差が1の等差数列の和を計算する関数 my_soap(sum of arithmetic progression) を考える。

my_soap 0 = 0
my_soap 1 = 0 + 1
my_soap 2 = 0 + 1 + 2
my_soap 3 = 0 + 1 + 2 + 3
my_soap 4 = 0 + 1 + 2 + 3 + 4

一歩手前を使うとどうなる？

my_soap 0 = 0
my_soap 1 = my_soap 0 + 1
my_soap 2 = my_soap 1 + 2
my_soap 3 = my_soap 2 + 3
my_soap 4 = my_soap 3 + 4

再帰部を一般化するとどうなる？

my_soap :: Integer -> Integer
my_soap 0 = 0                 -- 基底部
my_soap n = my_soap (n-1) + n -- 再帰部

##階乗

階乗を計算する関数 my_fact を考える。

my_fact 1 = 1
my_fact 2 = 1 * 2
my_fact 3 = 1 * 2 * 3
my_fact 4 = 1 * 2 * 3 * 4
my_fact 5 = 1 * 2 * 3 * 4 * 5

一歩手前を使うとどうなる？

my_fact 1 = 1
my_fact 2 = my_fact 1 * 2
my_fact 3 = my_fact 2 * 3
my_fact 4 = my_fact 3 * 4
my_fact 5 = my_fact 4 * 5

再帰部を一般化するとどうなる？

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

##掛け算

掛け算する関数 my_mul を考える。

my_mul m 1 = m
my_mul m 2 = m + m
my_mul m 3 = m + m + m
my_mul m 4 = m + m + m + m
my_mul m 5 = m + m + m + m + m

一歩手前を使うとどうなる？

my_mul m 1 = m
my_mul m 2 = my_mul m 1 + m
my_mul m 3 = my_mul m 2 + m
my_mul m 4 = my_mul m 3 + m
my_mul m 5 = my_mul m 4 + m

再帰部を一般化するとどうなる？

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

##演習

###足し算

my_plus m 0 = m
my_plus m 1 = m + 1
my_plus m 2 = m + 1 + 1
my_plus m 3 = m + 1 + 1 + 1
my_plus m 4 = m + 1 + 1 + 1 + 1

これの再帰的な定義を考えなさい。

my_plus :: Integer -> Integer -> Integer
my_plus = undefined

###引き算

my_minus m 0 = m
my_minus m 1 = m - 1
my_minus m 2 = m - 1 - 1
my_minus m 3 = m - 1 - 1 - 1
my_minus m 4 = m - 1 - 1 - 1 - 1

これの再帰的な定義を考えなさい。

my_minus :: Integer -> Integer -> Integer
my_minus = undefined

###累乗

my_power m 0 = 1
my_power m 1 = 1 * m
my_power m 2 = 1 * m * m
my_power m 3 = 1 * m * m * m
my_power m 4 = 1 * m * m * m * m
my_power m 5 = 1 * m * m * m * m * m

これの再帰的な定義を考えなさい。

my_power :: Integer -> Integer -> Integer
my_power = undefined

[目次] [演習1]