プログラミング論 I 関数の再帰呼び出し http://www.ns.kogakuin.ac.jp/~ct13140/Prog/

概要 関数 関数を再帰的に使用する 前期で最も重要な事項 後期で最も重要な事項 結構難しいです． 関数の作成 と 呼び出し がC言語の真骨頂 ポインタ

関数の多段呼び出し 0/3 実行結果 main() func0() func0() func0 start! func0 end! 1 void func0(){ 2 printf("func0 start!\n"); 3 printf("func0 end!\n"); 4 } 10 void main(){ 11 func0(); 12 } main() func0() 実行結果 func0() func0 start! func0 end!

関数の多段呼び出し 1/3 実行結果 1 void func0(){ 2 printf("func0 start!\n"); 3 printf("func0 end!\n"); 4 } 5 void func1(){ 6 printf("func1 start!\n"); 7 func0(); 8 printf("func1 end!\n"); 9 } 10 void main(){ 11 func1(); 12 } 実行結果 func1 start! func0 start! func0 end! func1 end!

関数の多段呼び出し 2/3 func0() func0() func1() func1() main()

関数の再帰呼び出し ある関数から，自分自身を呼び出すことを再帰呼び出しという． 例えば，関数funct() の中で，funct() を呼び出すなど． 使い方を間違えると，永遠に終了しないプログラムになりやすいので注意．

関数の再帰呼び出し 1 void pr_hl(){ 2 printf("Hello!start\n"); 3 pr_hl(); 4 printf("Hello!end\n"); 5 } 6 void main(){ 7 pr_hl(); 8 } 動作の解説は次ページ 注意！これは失敗例です．

呼び出しを永遠に続け， このプログラムは 終わらない． main() pr_hl()が 呼ばれたので， pr_hl()に移動．

再帰：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!

再帰：nの階乗 1/5 nの階乗は もし n == 1 なら， 答えは，1 もし n > 1 なら， 答えは，n×(n-1)!

再帰：nの階乗 2/5 1 int kaijoh(int x){ 2 int r; 3 if( x == 1 ){ 4 return 1; 5 } else { 6 r = x * kaijoh(x-1); 7 return r; 8 } 9 } 10 void main(){ 11 int n, k; 12 n = 5; 13 k = kaijoh( n ); 14 printf("%d! = %d\n", n, k); 15 }

再帰：nの階乗 3/5 main() kaijoh(3) kaijoh(3)は，3*kaijoh(2) kaijoh(2) これ以上再帰呼び出ししない． これがないと 無限に続く kaijoh(2)=2 kaijoh(3)は，3*2 kaijoh(3)=6

再帰：nの階乗 4/5 kaijoh( 4 ) =4* kaijoh( 3 ) =4* (3* kaijoh( 2 ) ) =4* (3* (2* 1 ) ) =4* (3* ( 2 ) ) =4* ( 6 ) =24

失敗例 1 int kaijoh(int x){ 2 int r; 3 r = x * kaijoh(x-1); 4 return r; ↓ kaijoh(4)を呼び出し kaijoh(3)を呼び出し kaijoh(2)を呼び出し kaijoh(1)を呼び出し kaijoh(0)を呼び出し kaijoh(-1)を呼び出し kaijoh(-2)を呼び出し kaijoh(-3)を呼び出し 無限に続く 1 int kaijoh(int x){ 2 int r; 3 r = x * kaijoh(x-1); 4 return r; 5 } 6 void main(){ 7 int n, k; 8 n = 5; 9 k = kaijoh( n ); 10 printf("%d! = %d\n", n, k); 11 }

再帰：組み合わせ nCr 組み合わせ(Conbination) nCr は， r>1なら， nCr=n-1Cr-1 * n / r

再帰：ハノイの塔 ハノイの塔というパズル ルール 円盤置き場が3カ所ある． 円盤がn枚あり，全て大きさが異なる． 通常，円盤の中心に穴があり， 円盤置き場には杭が立っている． 円盤がn枚あり，全て大きさが異なる． 小さい円盤の上に大きな円盤は置けない． 円盤置き場の1番上の1枚を別の円盤置き場に移動することができる． 引用 奥野かるた店より http://www.okunokaruta.com/ goods/goods12e10.jpg

再帰：ハノイの塔 目的 解法 n枚の円盤を，ある円盤置き場から別の円盤置き場に移動する． できるだけ少ない円盤移動が好ましい． 最適解は， 円盤がn枚の場合，2n-1回の円盤移動． プログラミングでは，再帰的手法で解ける．

ハノイの塔：2枚の例 円盤 1 2 円盤置き場 ↓開始！(円盤2枚を左から中央に) 1 2 1回目の移動． 円盤1を左から右に． 2 1

ハノイの塔：2枚の例 2 1 2回目の移動． 円盤2を左から中央に． 2 1 2 1 3回目の移動． 円盤1を右から中央に． 22-1=3回で終了． 1 2 完了！

ハノイの塔：3枚の例 1 2 1回目の移動． 円盤1を左から中央に． 3 2 2回目の移動． 円盤2を左から右に． 円盤3の上が空に． 3 3回目の移動． 円盤1を中央から右に． 中央の円盤置き場が 空いた．円盤3を 中央に移動可能． 1 3 2

ハノイの塔：3枚の例 4回目の移動． 円盤3を左から中央に． ついに円盤3が移動！ 1 3 2 1 5回目の移動． 円盤1を左から右に． 3 6回目の移動． 円盤2を右から中央に． 1 3 2 2 7回目の移動． 円盤1を左から中央に． 1 3 1 2 3

ハノイの塔：4枚の例 24-1=15回の移動． 円盤3枚の移動方法(7回)は分かっている．．． ↓ 円盤3枚の移動方法を使えば， 円盤4枚の移動方法を導き出せる．

ハノイの塔：4枚の例 合計 7+1+7=15回 1 先ほどの方法で， 円盤3枚(1～3)を 左から右に移動． 7回の円盤移動． 2 3 4 円盤4を左から中央に． 1回の円盤移動． 4 3 1 先ほどの方法で， 円盤3枚(1～3)を 右から中央に移動． 7回の円盤移動． 2 4 3 1 2 3 合計 7+1+7=15回 4

ハノイの塔：5枚の例 合計 15+1+15=31回 1 先ほどの方法で， 円盤4枚(1～4)を 左から右に移動． 15回の円盤移動． : 4 円盤5を左から中央に． 1回の円盤移動． 5 4 1 先ほどの方法で， 円盤4枚(1～4)を 右から中央に移動． 15回の円盤移動． : 5 4 1 : 4 合計 15+1+15=31回 5

ハノイの塔：n枚 合計 (2n-1)+1+(2n-1)=2n+1-1回 1 : n枚を左から右に 移動する． 移動回数2n-1回． n 移動回数1回． : n+1 n 1 : n枚を右から中央に 移動する． 移動回数2n-1回． n+1 n 1 : n 合計 (2n-1)+1+(2n-1)=2n+1-1回 n+1

ハノイの塔：n枚 n枚の移動方法が分かれば， それを用いて n+1枚の移動方法が分かる． 1枚の移動方法は分かる． ↓ 任意の枚数の移動方法が分かる

ハノイの塔を解く関数 ハノイの塔の移動(移動枚数，移動元の円盤置場，移動先の円盤置場，待避円盤置場) もし，移動枚数が1なら， 1枚を「移動元」から「移動先」に移動する． もし，移動枚数が1より大きければ， (n-1)枚を「移動元」から「待避」に移動． n枚目を「移動元」から「移動先」に移動． (n-1)枚を「待避」から「移動先」に移動．

ハノイの塔を解く関数 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); hanoi(n-1, plOther, plTo, plFrom); } void main(){ hanoi(5, 0, 1, 2);

フィボナッチ数列 以下の数列がフィボナッチ数列 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文で加算した方が短時間で計算可能

フィボナッチ数列 fibo(5) fibo(4) fibo(3) fibo(1) =1 fibo(2) fibo(3) fibo(2) 同じ処理を何度も 行っている． 大変に非効率的 fibo(0) =1 fibo(1) =1 fibo(0) =1 fibo(1) =1

計算量/計算時間 n枚のハノイの塔 n個の数字をバブルソートで並び替える． n個の数字をクイックソートで並び替える n×log(n) に比例する計算量/時間 n個の数字をバケツソートで並び替える n に比例する計算量/時間

練習 (い) fibo(n)=fibo(n-1)+fibo(n-2) という 再帰的な考え方で,

解答 (い) #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)); これは例