1. No category

計算機数学演習 A 2014.5.16. Risa/Asir のプログラミング (再帰)
この講義の資料は, http://www.sm.u-tokai.ac.jp/~nakayama/ より入手することができる.
1. 再帰
関数の中から, その関数を再び呼び出すことを再帰という.
例 1. 次は, 再帰を使って階乗 n! を計算する関数の例である. 階乗 n! (n は自然数) は次のように定義できる.

n · (n − 1)! (n > 1)
n! =
1
(n = 1)
例えば, 上の定義を使って 4! は,
4! = 4 · 3! = 4 · 3 · 2! = 4 · 3 · 2 · 1! = 4 · 3 · 2 · 1
となる. この定義を素直に関数の形に書いたものが次である.
✓
✏
factorial.rr
def factorial(N)
{
if (N > 1)
return N * factorial(N - 1);
else
return 1;
}
end$
✒
✑
例 2. 次は, 再帰を使ってフィボナッチ数列 {fn } を計算する関数の例である. フィボナッチ数列 {fn } は次のよ



f
+ fn−2

 n−1
fn = 1



1
うに漸化式で定義される.
(n ≥ 3)
(n = 2)
(n = 1)
この定義に素直にしたがって, 関数を書くと次のようになる. (ただし, 計算の効率は非常に悪いものである.)
✓
✏
r fib.rr
def r_fib(N)
{
if (N >= 3)
return r_fib(N - 1) + r_fib(N - 2);
else if (N == 2)
return 1;
else
return 1;
}
end$
✒
✑
例 3. 次は, 再帰を使って組合せの数 (二項係数) n Cr を計算する例である. 組合せの数 (二項係数) n Cr は次



C
+
C

n−1 r−1 n−1 r
のように定義される.
n Cr
=
0



1
(n ≥ r ≥ 1)
(r > n)
(r = 0)
この定義に素直にしたがって, 関数を書くと次のようになる. (ただし, 計算の効率は非常に悪いものである.)
1
✓
r comb.rr
def r_comb(N, R)
{
if (N >= R && R >= 1)
return r_comb(N - 1, R - 1) + r_comb(N - 1, R);
else if (R > N)
return 0;
else
return 1;
}
end$
✒
✏
✑
例 4. チェビシェフ多項式 Tn (x) とは次のように定義される x の n 次多項式である.



−T
(x) + 2xTn−1 (x) (n ≥ 3)

 n−2
Tn (x) = T1 (x) = x



T (x) = 2x2 − 1
2
この定義に素直にしたがって, 関数を書くと次のようになる. (ただし, 計算の効率は非常に悪いものである.)
✓
r cheb.rr
def r_cheb(N)
{
if (N >= 3)
return -r_cheb(N - 2) + 2 * x * r_cheb(N - 1);
else if (N == 1)
return 1;
else
return 2 * x^2 - 1;
}
end$
✒
チェビシェフ多項式は次の性質がある.
cos(nθ) = Tn (cos θ)
すなわち, n 次のチェビシェフ多項式は cos の n 倍角の公式を与える.
例 5. 次の関数 perm は順列を生成する関数である. 例えば, perm([1,2,3]); とすると, 1, 2, 3 の順列全て
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] を返す.
アイデアは, 1, 2, 3 の順列は,
• 2, 3 の順列それぞれの先頭に 1 を付け加えたもの,
• 1, 3 の順列それぞれの先頭に 2 を付け加えたもの,
• 1, 2 の順列それぞれの先頭に 3 を付け加えたもの,
からなる.
2
✏
✑
✓
perm.rr
✏
def perm(L)
<--- L の順列を全て生成する
{
if (length(L) <= 1)
return [L];
LL = [];
for (I = 0; I < length(L); I++) {
T = L[I];
TL = del_l(L, I);
LL = append(LL, cons_l(T, perm(TL)));
}
return LL;
}
def del_l(L, N)
<--- リスト L の第 N 番目の成分を削除したリスト
{
LL = [];
for (I = 0; I < length(L); I++)
if (I != N)
LL = cons(L[I], LL);
return reverse(LL);
}
def cons_l(A, L) <--- リスト L は各成分がリストからなるものとする. L の各成分のリストの先頭に A を追加
{
LL = [];
for (I = 0; I < length(L); I++)
LL = cons(cons(A, L[I]), LL);
return reverse(LL);
}
end$
✒
3
✑