プログラミング論

プログラミング論 I
関数の再帰呼び出し
http://www.ns.kogakuin.ac.jp/~ct13140/Prog/
F-1
概要
• 関数を再帰的に使用する
– 結構難しいです.
– 関数の作成 と 呼び出し
– がC言語の真骨頂
• 前期で最も重要な事項
–関数
• 後期で最も重要な事項
– ポインタ
F-2
関数の多段呼び出し 0/3
1
2
3
4
10
11
12
void func0(){
printf("func0 start!¥n");
printf("func0 end!¥n");
}
void main(){
main()
func0();
}
func0()
実行結果
func0()
func0 start!
func0 end!
F-3
関数の多段呼び出し 1/3
1
2
3
4
5
6
7
8
9
10
11
12
void func0(){
printf("func0
printf("func0
}
void func1(){
printf("func1
func0();
printf("func1
}
void main(){
func1();
}
start!¥n");
end!¥n");
start!¥n");
end!¥n");
実行結果
func1
func0
func0
func1
start!
start!
end!
end!
F-4
関数の多段呼び出し 2/3
func0()
func1()
func0()
func1()
main()
F-5
関数の再帰呼び出し
• ある関数から,自分自身を呼び出すことを
再帰呼び出しという.
– 例えば,関数funct() の中で,funct() を
呼び出すなど.
• 使い方を間違えると,永遠に終了しないプ
ログラムになりやすいので注意.
F-6
関数の再帰呼び出し
1
2
3
4
5
6
7
8
void pr_hl(){
printf("Hello!start\n");
pr_hl();
printf("Hello!end\n");
}
void main(){
pr_hl();
}
動作の解説は次ページ
注意!これは失敗例です.
F-7
pr_hl()が
呼ばれたので,
pr_hl()に移動.
main()
pr_hl()
呼び出しを永遠に続け,
このプログラムは
終わらない.
pr_hl()
main()から,
pr_hl()が
呼ばれたので,
pr_hl()に移動.
pr_hl()
pr_hl()
F-8
再帰:nの階乗 0/5
• nの階乗を,n!と記述する.
• n! は,n×(n-1)×(n-2)×…×2×1
• n! は,n × (n-1)!
• 5! は,5×4×3×2×1
• 5! は,5×4!
F-9
再帰:nの階乗 1/5
• nの階乗は
もし n == 1 なら,
答えは,1
もし n > 1 なら,
答えは,n×(n-1)!
上(n==1)が無いと,永遠に終わらない
F-10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int kaijoh(int x){
int r;
if( x == 1 ){
return 1;
} else {
r = x * kaijoh(x-1);
return r;
}
}
void main(){
int n, k;
n = 5;
k = kaijoh( n );
printf("%d! = %d\n", n, k);
}
再帰:nの階乗 2/5
F-11
main()
再帰:nの階乗 3/5
kaijoh(3)
kaijoh(3)は,3*kaijoh(2)
kaijoh(2)
kaijoh(2)は,2*kaijoh(1)
kaijoh(1)
kaijoh(1)は,1
kaijoh(1)=1
kaijoh(1)=1
kaijoh(2)=2
kaijoh(2)は,2*1
kaijoh(2)=2
kaijoh(3)は,3*2
kaijoh(3)=6
n==1の時は,
これ以上再帰呼
び出ししない.
これがないと
無限に続く
F-12
再帰:nの階乗 4/5
kaijoh(
4
=4* kaijoh(
3
=4* (3* kaijoh( 2
=4* (3* (2* kaijoh(1)
=4* (3* (2*
1
=4* (3* (
2
=4* (
6
=24
)
)
)
)
)
)
)
)
)
)
)
F-13
失敗例
1
2
3
4
5
6
7
8
9
10
11
int kaijoh(int x){
int r;
r = x * kaijoh(x-1);
return r;
}
void main(){
int n, k;
n = 5;
k = kaijoh( n );
printf("%d! = %d\n", n, k);
}
kaijoh(5)を呼び出し
↓
kaijoh(4)を呼び出し
↓
kaijoh(3)を呼び出し
↓
kaijoh(2)を呼び出し
↓
kaijoh(1)を呼び出し
↓
kaijoh(0)を呼び出し
↓
kaijoh(-1)を呼び出し
↓
kaijoh(-2)を呼び出し
↓
kaijoh(-3)を呼び出し
↓
無限に続く
F-14
再帰:組み合わせ nCr
• 組み合わせ(Conbination)
nCr は,
r>1なら, nCr=n-1Cr-1 * n / r
r==1なら, nCr=n
F-15
再帰:ハノイの塔
• ハノイの塔というパズル
• ルール
– 円盤置き場が3カ所ある.
通常,円盤の中心に穴があり,
円盤置き場には杭が立っている.
引用 奥野かるた店より
http://www.okunokaruta.com/
goods/goods12e10.jpg
– 円盤がn枚あり,全て大きさが異なる.
– 小さい円盤の上に大きな円盤は置けない.
– 円盤置き場の1番上の1枚を別の円盤置き場
に移動することができる.
F-16
再帰:ハノイの塔
• 目的
– n枚の円盤を,ある円盤置き場から別の円盤
置き場に移動する.
– できるだけ少ない円盤移動が好ましい.
• 解法
– 最適解は,
円盤がn枚の場合,2n-1回の円盤移動.
– プログラミングでは,再帰的手法で解ける.
F-17
ハノイの塔:2枚の例
1
2
↓開始!(円盤2枚を左から中央に)
1
2
2
円盤
円盤置き場
1回目の移動.
円盤1を左から右に.
1
F-18
ハノイの塔:2枚の例
2
1
2
1
2
1
1
2
2回目の移動.
円盤2を左から中央に.
3回目の移動.
円盤1を右から中央に.
22-1=3回で終了.
完了!
F-19
ハノイの塔:3枚の例
1
2
3
1回目の移動.
円盤1を左から中央に.
2
3
1
3
1
3
2回目の移動.
円盤2を左から右に.
円盤3の上が空に.
2
1
2
3回目の移動.
円盤1を中央から右に.
中央の円盤置き場が
空いた.円盤3を
中央に移動可能.
F-20
ハノイの塔:3枚の例
1
2
3
3
1
2
1
3
2
1
2
3
1
2
3
4回目の移動.
円盤3を左から中央に.
ついに円盤3が移動!
5回目の移動.
円盤1を左から右に.
6回目の移動.
円盤2を右から中央に.
7回目の移動.
円盤1を左から中央に.
F-21
ハノイの塔:4枚の例
1
2
3
4
• 24-1=15回の移動.
• 円盤3枚の移動方法(7回)は分かってい
る...
↓
• 円盤3枚の移動方法を使えば,
円盤4枚の移動方法を導き出せる.
F-22
ハノイの塔:4枚の例
1
2
3
4
先ほどの方法で,
円盤3枚(1~3)を
左から右に移動.
7回の円盤移動.
1
2
3
4
4
1
2
3
4
1
2
3
円盤4を左から中央に.
1回の円盤移動.
先ほどの方法で,
円盤3枚(1~3)を
右から中央に移動.
7回の円盤移動.
合計 7+1+7=15回 F-23
ハノイの塔:5枚の例
1
:
4
5
先ほどの方法で,
円盤4枚(1~4)を
左から右に移動.
15回の円盤移動.
1
:
4
5
5
1
:
4
5
1
:
4
円盤5を左から中央に.
1回の円盤移動.
先ほどの方法で,
円盤4枚(1~4)を
右から中央に移動.
15回の円盤移動.
合計 15+1+15=31回F-24
ハノイの塔:n枚
1
:
n
n+1
n枚を左から右に
移動する.
移動回数2n-1回.
1
:
n
n+1
n+1
1
:
n
n+1
1
:
n
円盤n+1を左から中央に.
移動回数1回.
n枚を右から中央に
移動する.
移動回数2n-1回.
合計 (2n-1)+1+(2n-1)=2n+1-1回
F-25
ハノイの塔:n枚
• n枚の移動方法が分かれば,
それを用いて n+1枚の移動方法が分かる.
• 1枚の移動方法は分かる.
↓
• 任意の枚数の移動方法が分かる
F-26
ハノイの塔を解く関数
• ハノイの塔の移動(移動枚数,移動元の円盤置
場,移動先の円盤置場,待避円盤置場)
もし,移動枚数が1なら,
1枚を「移動元」から「移動先」に移動する.
もし,移動枚数が1より大きければ,
(n-1)枚を「移動元」から「待避」に移動.
n枚目を「移動元」から「移動先」に移動.
(n-1)枚を「待避」から「移動先」に移動.
F-27
ハノイの塔を解く関数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
void hanoi(int n, int plFrom, int plTo, int plOther){
if( n == 1 ){
printf("move disk.%d ", n);
printf("[%d -> %d]\n", plFrom, plTo);
} else {
hanoi(n-1, plFrom, plOther, plTo);
printf("move disk.%d ", n);
printf("[%d -> %d]\n", plFrom, plTo);
hanoi(n-1, plOther, plTo, plFrom);
}
}
void main(){
hanoi(5, 0, 1, 2);
}
F-28
フィボナッチ数列
• 以下の数列がフィボナッチ数列
1,1,2,3,5,8,13,21,34,…
an+an+1=an+2 となる.
ただし,a0=1,a1=1
• fibo(n)=fibo(n-1)+fibo(n-2)
という再帰的な発想で記述可能.
– ただし,for文で加算した方が短時間で計算可能
F-29
フィボナッチ数列
fibo(5)
fibo(4)
fibo(3)
fibo(2)
fibo(1)
=1
fibo(2)
fibo(0) fibo(1)
=1
=1
fibo(3)
fibo(1)
=1
fibo(2)
fibo(0) fibo(1)
=1
=1
f(2)計算などの,
同じ処理を何度も
fibo(0) fibo(1)
行っている.
=1
=1
大変に非効率的
F-30
計算量/計算時間
• n枚のハノイの塔
– 2n-1回 ≒ 2n に比例する計算量/時間
• n個の数字をバブルソートで並び替える.
– n2 に比例する計算量/時間
• n個の数字をクイックソートで並び替える
– n×log(n) に比例する計算量/時間
• n個の数字をバケツソートで並び替える
– n に比例する計算量/時間
F-31
練習 (い)
• fibo(n)=fibo(n-1)+fibo(n-2)
という 再帰的な考え方で,
フィボナッチ数列の第n項を求める関数を
記述せよ.
F-32
解答 (い)
#include <stdio.h>
int fibo(int n){
if( n <= 1 ){
return 1;
} else {
return fibo(n-1)+fibo(n-2);
}
}
void main(){
printf("%d\n", fibo(7));
}
これは例
F-33