ホーム » 「再帰方程式」タグがついた投稿

タグアーカイブ: 再帰方程式

2023年11月
日	月	火	水	木	金	土
	1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30

再帰呼び出しと処理時間の見積もり

2023年4月25日

再帰呼び出しの基本

次に、再帰呼び出しを含むような処理の処理時間見積もりについて解説をおこなう。そのまえに、再帰呼出しと簡単な処理の例を説明する。

再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。プログラムには問題が最小となった時の処理があることで、再帰の繰り返しが止まる。

// 階乗 (末尾再帰)
int fact( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x * fact( x-1 ) ;
}
// ピラミッド体積 (末尾再帰)
int pyra( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x*x + pyra( x-1 ) ;
}
// フィボナッチ数列 (非末尾再帰)
int fib( int x ) {
   if ( x <= 2 )
      return 1 ;
   else
      return fib( x-1 ) + fib( x-2 ) ;
}

階乗 fact(N) を求める処理は、以下の様に再帰が進む。

また、フィボナッチ数列 fib(N) を求める処理は以下の様に再帰が進む。

再帰呼び出しの処理時間

次に、この再帰処理の処理時間を説明する。最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、T(1)=T_a で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理(T_b)に加え、x-1の値で再帰を実行する処理時間T(N-1)がかかる。このことから、 T(N)=T_b=T(N-1)で表せる。

${T(1)}=T_a$ } 再帰方程式

${T(N)}=T_b+T(N-1)$

このような、式の定義自体を再帰を使って表した式は再帰方程式と呼ばれる。これを以下のような代入の繰り返しによって解けば、一般式 ${T(N)}=T_a-T_b+N T_b$ が得られる。

T(1)=T_a
T(2)=T_b+T(1)=T_b+T_a
T(3)=T_b+T(2)=2×T_b+T_a
:
T(N)=T_b+T(N-1)=T_b+ (N-2)×T_b+T_a

一般的に、再帰呼び出しプログラムは(考え方に慣れれば)分かりやすくプログラムが書けるが、プログラムを実行する時には、局所変数や関数の戻り先を覚える必要があり、深い再帰ではメモリ使用量が多くなる。
ただし、fact() や pyra() のような関数は、プログラムの末端で再帰が行われている。(fib()は、再帰の一方が末尾ではない)
このような再帰は、末尾再帰(tail recursion) と呼ばれ、関数呼び出しの return を、再帰処理の先頭への goto 文に書き換えるといった最適化が可能である。言い換えるならば、末尾再帰の処理は繰り返し処理に書き換えが可能である。このため、末尾再帰の処理をループにすれば再帰のメモリ使用量の問題を克服できる。

再帰を含む一般的なプログラム例

ここまでのfact()やpyra()のような処理の再帰方程式は、再帰の度にNの値が1減るものばかりであった。もう少し一般的な再帰呼び出しのプログラムを、再帰方程式で表現し、処理時間を分析してみよう。
以下のプログラムを実行したらどんな値になるであろうか？それを踏まえ、処理時間はどのように表現できるであろうか？

int array[ 8 ] = {
  3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
} ;

int sum( int a[] , int L , int R ) { // 非末尾再帰
    if ( R - L == 1 ) {
        return a[ L ] ;
    } else {
        int M = (L + R) / 2 ;
        return sum( a , L , M ) + sum( a , M , R ) ;
    }
}
int main() {
    printf( "%d¥n" , sum( array , 0 , 8 ) ) ;
    return 0 ;
}

このプログラムでは、配列の合計を計算しているが、引数の L,R は、合計範囲の左端(左端のデータのある場所)・右端(右端のデータのある場所+1)を表している。そして、再帰のたびに２つに分割して解いている。

このような、処理を(この例では半分に)分割し、分割したそれぞれを再帰で計算し、その処理結果を組み合わせて最終的な結果を求めるような処理方法を、分割統治法と呼ぶ。

このプログラムでは、対象となるデータ件数(R-L)をNとおいた場合、実行される命令からsum()の処理時間T_s(N)は次の再帰方程式で表せる。

${T_s(1)=T_{\alpha}}$

${T_s(N)=T_{\beta}+2\times{T_s(\frac{N}{2})}}$ ← T_β + (L〜M)の処理時間 + (M〜R)の処理時間

これを代入の繰り返しで解いていくと、

${T_s(1)=T_{\alpha}}$

${T_s(2)=T_{\beta}+2\times T_{\alpha}}$

${T_s(4)=T_{\beta}+2\times T_s(2) = 3\times T_{\beta}+4\times T_{\alpha}}$

${T_s(N)=(N-1) T_{\beta} + N T_{\alpha} = -T_{\beta} + N(T_{\alpha}+T_{\beta})}$

ということで、このプログラムの処理時間は、 ${O(N)}$ で表せる。

ハノイの塔

ここまでは、簡単な再帰呼び出しのプログラムを例にして再帰方程式などの説明を行った。次に「ハノイの塔」の処理時間を例題に、プログラムの処理時間について分析を行う。

ハノイの塔は、３本の塔にN枚のディスクを積み、(1)1回の移動ではディスクを1枚しか動かせない、(2)ディスクの上により大きいディスクを積まない…という条件で、山積みのディスクを目的の山に移動させるパズル。

一般解の予想

ハノイの塔の移動回数を ${H(N)}$ とした場合、少ない枚数での回数の考察から、以下の一般式で表せることが予想できる。

${H(N)}=2^N-1$ … ①

この予想が常に正しいことを証明するために、ハノイの塔の処理を、最も下のディスク1枚への操作と、その上の(N-1)枚のディスクへの操作に分けて考える。

再帰方程式

上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、

${H(1)}=1$ … ②
${H(N)}=1+2H(N-1)$ 　… ③

ということが言える。(これがハノイの塔の移動回数の再帰方程式)
ディスクが ${k=1}$ 枚の時、予想①が正しいのは明らか①,②。
ディスクが ${k}$ 枚で、予想が正しいと仮定すると、 ${k+1}$ 枚では、

${H(k+1)}=1+2H(k)$ 　… ③より
${H(k+1)}=1+2(2^k-1)$ … ①を代入
${H(k+1)}=2^{k+1}-1$ … ①の ${k+1}$ の場合

となり、 ${k+1}$ 枚でも、予想が正しいことが証明された。よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

また、ハノイの塔の処理時間は、 ${O(2^N)}$ で表せる。

再帰呼び出しと再帰方程式

2022年5月9日

前回の授業では、簡単な再帰呼び出しのプログラムについて再帰方程式などの説明を行った。今日の授業では、ハノイの塔の処理時間や、マージソートのプログラムの処理時間について検討を行う。

ハノイの塔

一般解の予想

ハノイの塔の移動回数を ${H(N)}$ とした場合、少ない枚数での回数の考察から、以下の一般式で表せることが予想できる。

${H(N)}=2^N-1$ … ①

再帰方程式

上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、

${H(1)}=1$ … ②
${H(N)}=1+2H(N-1)$ 　… ③

ということが言える。(これがハノイの塔の移動回数の再帰方程式)
ディスクが ${k=1}$ 枚の時、予想が正しいのは明らか①,②。
ディスクが ${k}$ 枚で、予想が正しいと仮定すると、 ${k+1}$ 枚では、

${H(k+1)}=1+2H(k)$ 　… ③より
${H(k+1)}=1+2(2^k-1)$ … ①を代入
${H(k+1)}=2^{k+1}-1$

となり、 ${k+1}$ 枚でも、予想が正しいことが証明された。よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

理解度確認

前再帰の「ピラミッドの体積」pyra() を、ループにより計算するプログラムを記述せよ。
前講義での2分探索法のプログラムを、再帰によって記述せよ。(以下のプログラムを参考に)。また、このプログラムの処理時間にふさわしい再帰方程式を示せ。

int a[ 10 ] = {
   7 , 12 , 22 , 34 , 41 , 56 , 62 , 78 , 81 , 98
} ;
int find( int array[] , int L , int R , int key ) { // 末尾再帰
   // 目的のデータが見つかったら 1,見つからなかったら 0 を返す。
   if ( __________ ) {
      return ____ ; // 見つからなかった
   } else {
      int M = _________ ;
      if ( array[ M ] == key )
         return ____ ;
      else if ( array[ M ] > key )
         return find( array , ___ , ___ , key ) ;
      else
         return find( _____ , ___ , ___ , ___ ) ;
   }
}
int main() {
   if ( find( a , 0 , 10 , 56 ) )
      printf( "みつけた¥n" ) ;
}

再帰を使ったソートアルゴリズムの分析

データを並び替える有名なアルゴリズムの処理時間のオーダは、以下の様になる。

バブルソート $O(N^2)$
選択法 $O(\frac{N^2}{2})$
※本来は1/2は比例定数なのでオーダの中には書かない。ただし比較計算量がバブルソートの半分であることを強調する時は、この様に書くことが多い。
クイックソート $O(N\log{N})$
マージソート
- 参考：ソートアルゴリズム12種を可視化してみた

この中で、高速なソートアルゴリズムは、クイックソート(最速のアルゴリズム)とマージソート(オーダでは同程度だが若干効率が悪い)であるが、ここでは、再帰方程式で処理時間をイメージしやすい、マージソートにて説明を行う。

マージソートの分析

マージソートは、与えられたデータを2分割し、その2つの山をそれぞれマージソートを行う。この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、ソートを行う。

参考: マージソート(併合整列法)

このことから、再帰方程式は、以下のようになる。

$Tm(1)=Ta$
$T_M(N)=2T_M(\frac{N}{2})+NT_b+T_c$

この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、最終的に処理時間のオーダが $O(N \log{N})$ となる。

$T_M(1)=T_a$
$T_M(2)=2T_M(1)+2T_b+Tc = 2T_a+2T_b+Tc$
$T_M(4)=2T_M(2)+4T_b+Tc = 4T_a+8T_b+3Tc$
：
$T_M(N)=NT_a+N\log{N}T_b+(N-1)Tc$
よって、処理時間のオーダは $O(N\log{N})$ となる。

選択法とクイックソートの処理時間の比較

データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。

データ件数 N = 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
データ件数何件以上なら、クイックソートの方が高速になるか答えよ。

設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓などが必要。[解説]

再帰呼び出しの処理時間の見積もり

2022年4月26日

前回の授業の復習と練習問題

前回の授業では、for ループによる繰り返し処理のプログラムについて、処理時間を T(N) の一般式で表現することを説明し、それを用いたオーダー記法について説明を行った。理解を確認するための練習問題を以下に示す。

練習問題

ある処理のデータ数Nに対する処理時間が、 ${T(N)}=T_a + T_b \times N^2+T_c \times 2^N$ であった場合、オーダー記法で書くとどうなるか？
${T(N)}=T_A$ の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか？また、このような処理時間となるアルゴリズムの例を答えよ。
${T(N)}=T_A+T_B\times\sqrt{N}+T_C\times\log{N}$ の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか？
(ヒント: ロピタルの定理)

1は、N→∞において、N²≪ 2^Nなので、O(2^N) 。厳密に回答するなら、練習問題3と同様の証明を行うべき。
2は、O(1)。誤答の例：O(0)と書いちゃうと、T(N)=T_α×0=0になってしまう。事例は、電話番号を、巨大配列の”電話番号”番目の場所に記憶するといった方法。(これはハッシュ法で改めて講義予定)
3の解説

再帰呼び出しの基本

次に、再帰呼び出しを含むような処理の処理時間見積もりについて解説をおこなう。そのまえに、再帰呼出しと簡単な処理の例を説明する。

// 階乗 (末尾再帰)
int fact( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x * fact( x-1 ) ;
}
// ピラミッド体積 (末尾再帰)
int pyra( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x*x + pyra( x-1 ) ;
}
// フィボナッチ数列 (非末尾再帰)
int fib( int x ) {
   if ( x <= 2 )
      return 1 ;
   else
      return fib( x-1 ) + fib( x-2 ) ;
}

階乗 fact(N) を求める処理は、以下の様に再帰が進む。

また、フィボナッチ数列 fib(N) を求める処理は以下の様に再帰が進む。

再帰呼び出しの処理時間

${T(1)}=T_a$ } 再帰方程式

${T(N)}=T_b+T(N-1)$

T(1)=T_a
T(2)=T_b+T(1)=T_b+T_a
T(3)=T_b+T(2)=2×T_b+T_a
:
T(N)=T_b+T(N-1)=T_b+ (N-2)×T_b+T_a

一般的に、再帰呼び出しプログラムは(考え方に慣れれば)分かりやすくプログラムが書けるが、プログラムを実行する時には、局所変数や関数の戻り先を覚える必要があり、深い再帰ではメモリ使用量が多くなる。
ただし、fact() や pyra() のような関数は、プログラムの末端で再帰が行われている。(fib()は、再帰の一方が末尾ではない)
このような再帰は、末尾再帰(tail recursion) と呼ばれ、関数呼び出しの return を、再帰処理の先頭への goto 文に書き換えるといった最適化が可能である。言い換えるならば、末尾再帰の処理は繰り返し処理に書き換えが可能である。このため、末尾再帰の処理をループにすれば再帰のメモリ使用量の問題を克服できる。

再帰を含む一般的なプログラム例

int array[ 8 ] = {
  3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
} ;

int sum( int a[] , int L , int R ) { // 非末尾再帰
    if ( R - L == 1 ) {
        return a[ L ] ;
    } else {
        int M = (L + R) / 2 ;
        return sum( a , L , M ) + sum( a , M , R ) ;
    }
}
int main() {
    printf( "%d¥n" , sum( array , 0 , 8 ) ) ;
    return 0 ;
}

このような、処理を(この例では半分に)分割し、分割したそれぞれを再帰で計算し、その処理結果を組み合わせて最終的な結果を求めるような処理方法を、分割統治法と呼ぶ。

このプログラムでは、対象となるデータ件数(R-L)をNとおいた場合、実行される命令からsum()の処理時間T_s(N)は次の再帰方程式で表せる。

${T_s(1)=T_{\alpha}}$

${T_s(N)=T_{\beta}+2\times{T_s(\frac{N}{2})}}$ ← T_β + (L〜M)の処理時間 + (M〜R)の処理時間

これを代入の繰り返しで解いていくと、

${T_s(1)=T_{\alpha}}$

${T_s(2)=T_{\beta}+2\times T_{\alpha}}$

${T_s(4)=T_{\beta}+2\times T_s(2) = 3\times T_{\beta}+4\times T_{\alpha}}$

${T_s(N)=(N-1) T_{\beta} + N T_{\alpha} = -T_{\beta} + N(T_{\alpha}+T_{\beta})}$

ということで、このプログラムの処理時間は、 ${O(N)}$ で表せる。

再帰呼び出しと再帰方程式

2021年4月26日

前回までの授業では、for ループの処理時間の分析や見積もりについて説明をしてきた。
次のテーマとして、再帰呼び出しを含む処理の処理時間の分析について説明する。

再帰関数と再帰方程式

// 階乗 (末尾再帰)
int fact( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x * fact( x-1 ) ;
}
// ピラミッド体積 (末尾再帰)
int pyra( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x*x + pyra( x-1 ) ;
}
// フィボナッチ数列 (非末尾再帰)
int fib( int x ) {
   if ( x <= 2 )
      return 1 ;
   else
      return fib( x-1 ) + fib( x-2 ) ;
}

これらの関数の結果について考えるとともに、この計算の処理時間を説明する。最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、T(1)=T_a で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理(T_b)に加え、x-1の値で再帰を実行する処理時間T(N-1)がかかる。このことから、 T(N)=T_b=T(N-1)で表せる。

${T(1)}=T_a$ } 再帰方程式

${T(N)}=T_b+T(N-1)$

T(1)=T_a
T(2)=T_b+T(1)=T_b+T_a
T(3)=T_b+T(2)=2×T_b+T_a
:
T(N)=T_b+T(N-1)=T_b+ (N-2)×T_b+T_a

一般的に、再帰呼び出しプログラムは(考え方に慣れれば)分かりやすくプログラムが書けるが、プログラムを実行する時には、局所変数や関数の戻り先を覚える必要があり、深い再帰ではメモリ使用量が多くなる。
ただし、fact() や pyra() のような関数は、プログラムの末端で再帰が行われている。(fib()は、再帰の一方が末尾ではない)
このような再帰は、末尾再帰(tail recursion) と呼ばれ、関数呼び出しの return を、再帰処理の先頭への goto 文に書き換えるといった最適化が可能である。言い換えるならば、末尾再帰の処理は繰り返し処理に書き換えが可能である。このため、末尾再帰の処理をループにすれば再帰のメモリ使用量の問題を克服できる。

再帰を含む一般的なプログラム例

int array[ 8 ] = {
  3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
} ;

int sum( int a[] , int L , int R ) { // 非末尾再帰
    if ( R - L == 1 ) {
        return a[ L ] ;
    } else {
        int M = (L + R) / 2 ;
        return sum( a , L , M ) + sum( a , M , R ) ;
    }
}
int main() {
    printf( "%d¥n" , sum( array , 0 , 8 ) ) ;
    return 0 ;
}

このような、処理を(この例では半分に)分割し、分割したそれぞれを再帰で計算し、その処理結果を組み合わせて最終的な結果を求めるような処理方法を、分割統治法と呼ぶ。

このプログラムでは、対象となるデータ件数(R-L)をNとおいた場合、実行される命令からsum()の処理時間T_s(N)は次の再帰方程式で表せる。

${T_s(1)=T_{\alpha}}$

${T_s(N)=T_{\beta}+2\times{T_s(\frac{N}{2})}}$ ← T_β + (L〜M)の処理時間 + (M〜R)の処理時間

これを代入の繰り返しで解いていくと、

${T_s(1)=T_{\alpha}}$

${T_s(2)=T_{\beta}+2\times T_{\alpha}}$

${T_s(4)=T_{\beta}+2\times T_s(2) = 3\times T_{\beta}+4\times T_{\alpha}}$

${T_s(N)=(N-1) T_{\beta} + N T_{\alpha} = -T_{\beta} + N(T_{\alpha}+T_{\beta})}$

ということで、このプログラムの処理時間は、 ${O(N)}$ で表せる。

次に、再帰方程式の事例として、ハノイの塔の処理時間について説明し、数学的帰納法での証明を示す。

ハノイの塔

一般解の予想

ハノイの塔の移動回数を ${H(N)}$ とした場合、少ない枚数での回数の考察から、以下の一般式で表せることが予想できる。

${H(N)}=2^N-1$ … ①

再帰方程式

上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、

${H(1)}=1$ … ②
${H(N)}=1+2H(N-1)$ 　… ③

${H(k+1)}=1+2H(k)$ 　… ③より
${H(k+1)}=1+2(2^k-1)$ … ①を代入
${H(k+1)}=2^{k+1}-1$

となり、 ${k+1}$ 枚でも、予想が正しいことが証明された。よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

理解度確認

前再帰の「ピラミッドの体積」pyra() を、ループにより計算するプログラムを記述せよ。
前講義での2分探索法のプログラムを、再帰によって記述せよ。(以下のプログラムを参考に)。また、このプログラムの処理時間にふさわしい再帰方程式を示せ。
再帰のフィボナッチ関数 fib() の処理時間にふさわしい再帰方程式を示せ。

int a[ 10 ] = {
   7 , 12 , 22 , 34 , 41 , 56 , 62 , 78 , 81 , 98
} ;
int find( int array[] , int L , int R , int key ) { // 末尾再帰
   // 目的のデータが見つかったら 1,見つからなかったら 0 を返す。
   if ( __________ ) {
      return ____ ; // 見つからなかった
   } else {
      int M = _________ ;
      if ( array[ M ] == key )
         return ____ ;
      else if ( array[ M ] > key )
         return find( array , ___ , ___ , key ) ;
      else
         return find( _____ , ___ , ___ , ___ ) ;
   }
}
int main() {
   if ( find( a , 0 , 10 , 56 ) )
      printf( "みつけた¥n" ) ;
}

再帰を使ったソートアルゴリズム

データを並び替える有名なアルゴリズムの処理時間のオーダは、以下の様になる。

バブルソート $O(N^2)$
選択法 $O(\frac{N^2}{2})$
※本来は1/2は比例定数なのでオーダの中には書かない。ただし比較計算量がバブルソートの半分であることを強調する時は、この様に書くことが多い。
クイックソート $O(N\log{N})$
マージソート $O(N\log{N})$

マージソートの分析

このことから、再帰方程式は、以下のようになる。

$Tm(1)=Ta$
$T_M(N)=2T_M(\frac{N}{2})+NT_b+T_c$

この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、最終的に処理時間のオーダが $O(N \log{N})$ となる。

$T_M(1)=T_a$
$T_M(2)=2T_M(1)+2T_b+Tc = 2T_a+2T_b+Tc$
$T_M(4)=2T_M(2)+4T_b+Tc = 4T_a+8T_b+3Tc$
：
$T_M(N)=NT_a+N\log{N}T_b+(N-1)Tc$
よって、処理時間のオーダは $O(N\log{N})$ となる。

選択法とクイックソートの処理時間の比較

データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。

データ件数 N = 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
データ件数何件以上なら、クイックソートの方が高速になるか答えよ。

設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓などが必要。

再帰方程式の理解度確認の解答

2020年5月20日

再帰呼び出しと再起方程式の資料の中の「理解度確認」の解答

解答

pyraをループで

// pyra() をループで書いたら。
int pyra( int x ) {
   int ans = 0 ;
   for( int i = 1 ; i <= x ; i++ )
      ans += i * i ;
   return ans ;
}

2分探索法を再帰で

// 2分探索を再帰で書いたら
int find( int array[] , int L , int R , int key ) {
   if ( R == L ) {
      return 0 ; // みつからない
   } else {
      int M = (L + R) / 2 ;
      if ( array[ M ] == key )     // みつかった
         return 1 ;           
      else if ( array[ M ] > key ) // 左側にある - 末尾再帰
         return find( array , L , M , key ) ;
      else                         // 右側にある
         return find( array , M+1 , R , key ) ;
   }
}

このプログラムでは、検索する範囲がLとRで与えられ、この範囲の幅が再帰が呼び出される毎に半分になっていく。

であれば、処理時間は対象となるデータ件数 N = R – L によって、処理時間は変化するので、T(N) で考えると、(ただし途中でデータが見つからない最悪の場合で式を示す)

データ件数0件では、if,R==L,return 0の処理を行う。このため、以下の様な再帰方程式の細小時での処理時間は、

$T(0)=T_a$ … ①

となる。(find(件数=1)の次は必ずfind(件数=0)が実行されるので $T(1)=T_a$ でも良い。)

Nは整数という条件をつけないと、N=1/2, 1/4, 1/8…で止まらない…と勘違いする人もいるし、データ件数が1件になったら再帰がとまると考えた方が分かりやすいので、 $T(1)=T_a$ の方が都合がいいかな…

データが1以上の時で、対象データが L..Mの範囲にあるのなら、再帰の時に対象データ件数は半分になるから、if,R==L,else,if,array[M]==key,else-if,array[M]>keyの処理時間(T_b) と find(…,L,M,…) の処理時間を要するので、次の式となる。

$T(N)=T_b+T(\frac{N}{2})$ … ②

一方、(M+1)..Rの範囲にあるのなら同様に、if,R==L,else,if,array[M]==key,else-if,array[M]>key,elseの処理時間(T_c)と、find(…,M+1,R,…) の処理時間なので、

$T(N)=T_c+T(\frac{N-1}{2})$ … ③

となる。ただ、処理時間の見積もりでは厳密な分析が求められないので、(N-1)/2 だと一般式が複雑になるので、N/2 で考える。さらにT_bとT_cの処理時間は少しの時間の違いだし、確率1/2でT_bとT_cのどちらかを実行するので、その平均時間をT_bで表すことにすれば、③は②とほぼ同じと見なすことができるので、再帰方程式は①と②で良い。

fib()の再帰方程式

再帰のフィボナッチ数 fib() の処理時間に相応しい再帰方程式は、xの値(Nとする)が2以下の時は、return を実行するだけ。3以上の時は、if,else,return,+ の処理時間と、fib(x-2)の処理時間、fib(x-1)の処理時間を要する。

よって、再帰方程式は、以下の式となる。

$T(1)=T(2)=T_a$

$T(N)=T_b+T(N-2)+T(N-1)$

これを代入法で一般式を求めると、T(N)=fib(N-2)×T_b+fib(N+1)×T_aかな？よって、再帰のfib()の処理時間は、フィボナッチ数に比例する。ちなみに、フィボナッチ数はピネの公式で一般項が示されているので、処理時間のオーダーは、次式となる。

$O((\frac{1+sqrt{5}}{2})^N)=O(1.6^N)$

再帰呼び出しと再帰方程式

2020年5月13日

再帰関数と再帰方程式

// 階乗 (末尾再帰)
int fact( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x * fact( x-1 ) ;
}
// ピラミッド体積 (末尾再帰)
int pyra( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x*x + pyra( x-1 ) ;
}
// フィボナッチ数列 (非末尾再帰)
int fib( int x ) {
   if ( x <= 2 )
      return 1 ;
   else
      return fib( x-1 ) + fib( x-2 ) ;
}

これらの関数の結果について考えるとともに、この計算の処理時間を説明する。最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、 ${T(1)}=T_a$ で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理(T_b)に加え、x-1の値で再帰を実行する処理時間T(N-1)がかかる。このことから、 ${T(N)}=T_b+T(N-1)$ で表せる。

${T(1)}=T_a$ } 再帰方程式

${T(N)}=T_b+T(N-1)$

このような再帰を使って表した式は再帰方程式と呼ばれる。これを代入によって解けば、一般式 ${T(N)}=T_a-T_b+N T_b$ が得られる。

T(1)=T_a
T(2)=T_b+T(1)=T_b+T_a
T(3)=T_b+T(2)=2×T_b+T_a
:
T(N)=T_b+T(N-1)=T_b+ (N-2)×T_b+T_a

一般的に、再帰呼び出しプログラムは(考え方に慣れれば)分かりやすくプログラムが書けるが、プログラムを実行する時には、局所変数や関数の戻り先を覚える必要があり、深い再帰ではメモリ使用量が多くなる。
ただし、fact() や pyra() のような関数は、プログラムの末端で再帰が行われている。(fib()は、再帰の一方が末尾ではない)
このような再帰は、末尾再帰と呼ばれ、関数呼び出しの return を、再帰処理の先頭への goto 文に書き換えるといった最適化が可能である。言い換えるならば、末尾再帰の処理は繰り返し処理に書き換えが可能である。このため、末尾再帰の処理をループにすれば再帰のメモリ使用量の問題を克服できる。

再帰を含む一般的なプログラム例

ここまでの再帰方程式は、再帰の度にNの値が1減るものばかりであった。もう少し一般的な再帰呼び出しのプログラムを、再帰方程式で処理時間を分析してみよう。
以下のプログラムを実行したらどんな値になるであろうか？それを踏まえ、処理時間はどのように表現できるであろうか？

int array[ 8 ] = {
  3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
} ;

int sum( int a[] , int L , int R ) { // 非末尾再帰
    if ( R - L == 1 ) {
        return a[ L ] ;
    } else {
        int M = (L + R) / 2 ;
        return sum( a , L , M ) + sum( a , M , R ) ;
    }
}
int main() {
    printf( "%d¥n" , sum( array , 0 , 8 ) ) ;
    return 0 ;
}

このプログラムでは、配列の合計を計算しているが、引数の L,R は、合計範囲の左端・右端を表している。そして、再帰のたびに２つに分割して解いている。

このような、処理を分割し、分割したそれぞれを再帰で計算し、その処理結果を組み合わせて最終的な結果を求めるような処理方法を、分割統治法と呼ぶ。

このプログラムでは、対象となるデータ件数(R-L)をNとおいた場合、実行される命令からsum()の処理時間T_s(N)は次の再帰方程式で表せる。

${T_s(1)=T_{\alpha}}$

${T_s(N)=T_{\beta}+2\times{T_s(\frac{N}{2})}}$ ← T_β + (L〜M)の処理時間 + (M〜R)の処理時間

これを代入の繰り返しで解いていくと、

${T_s(1)=T_{\alpha}}$

${T_s(2)=T_{\beta}+2\times T_{\alpha}}$

${T_s(4)=T_{\beta}+2\times T_s(2) = 3\times T_{\beta}+4\times T_{\alpha}}$

${T_s(N)=(N-1) T_{\beta} + N T_{\alpha} = -T_{\beta} + N(T_{\alpha}+T_{\beta})}$

ということで、このプログラムの処理時間は、 ${O(N)}$ で表せる。

再帰方程式の事例として、ハノイの塔の処理時間について説明し、数学的帰納法での証明を示す。

ハノイの塔

ハノイの塔は、３本の塔にN枚のディスクを積み、(1)1回の移動ではディスクを1枚しか動かせない、(2)ディスクの上により大きいディスクを積まない…という条件で、山積みのディスクを目的の山に移動させるパズル。

一般解の予想

ハノイの塔の移動回数を ${H(N)}$ とした場合、少ない枚数での回数の考察から、以下の一般式で表せることが予想できる。

${H(N)}=2^N-1$ … ①

この予想が常に正しいことを証明するために、ハノイの塔の処理を、最も下のディスク1枚と、その上の(N-1)枚のディスクに分けて考える。

再帰方程式

上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、

${H(1)}=1$ … ②
${H(N)}=1+2H(N-1)$ 　… ③

${H(k+1)}=1+2H(k)$ 　… ③より
${H(k+1)}=1+2(2^k-1)$ … ①を代入
${H(k+1)}=2^{k+1}-1$

となり、 ${k+1}$ 枚でも、予想が正しいことが証明された。よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

理解度確認

前再帰の「ピラミッドの体積」pyra() を、ループにより計算するプログラムを記述せよ。
前講義での2分探索法のプログラムを、再帰によって記述せよ。(以下のプログラムを参考に)。また、このプログラムの処理時間にふさわしい再帰方程式を示せ。
再帰のフィボナッチ関数 fib() の処理時間にふさわしい再帰方程式を示せ。

int a[ 10 ] = {
   7 , 12 , 22 , 34 , 41 , 56 , 62 , 78 , 81 , 98
} ;
int find( int array[] , int L , int R , int key ) { // 末尾再帰
   // 目的のデータが見つかったら 1,見つからなかったら 0 を返す。
   if ( __________ ) {
      return ____ ; // 見つからなかった
   } else {
      int M = _________ ;
      if ( array[ M ] == key )
         return ____ ;
      else if ( array[ M ] > key )
         return find( array , ___ , ___ , key ) ;
      else
         return find( _____ , ___ , ___ , ___ ) ;
   }
}
int main() {
   if ( find( a , 0 , 10 , 56 ) )
      printf( "みつけた¥n" ) ;
}

再帰を使ったソートアルゴリズム

データを並び替える有名なアルゴリズムの処理時間のオーダは、以下の様になる。

バブルソート $O(N^2)$
選択法 $O(\frac{N^2}{2})$
※本来は1/2は比例定数なのでオーダの中には書かない。ただし比較計算量がバブルソートの半分であることを強調する時は、この様に書くことが多い。
クイックソート $O(N\log{N})$
マージソート $O(N\log{N})$

マージソートの分析

このことから、再帰方程式は、以下のようになる。

$Tm(1)=Ta$
$T_M(N)=2T_M(N/2)+NT_b+T_c$

この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、最終的に処理時間のオーダが $O(N \log{N})$ となる。

$T_M(1)=T_a$
$T_M(2)=2T_M(1)+2T_b+Tc = 2T_a+2T_b+Tc$
$T_M(4)=2T_M(2)+4T_b+Tc = 4T_a+8T_b+3Tc$
：
$T_M(N)=NT_a+N\log{N}T_b+(N-1)Tc$
よって、 $O(N\log{N})$

選択法とクイックソートの処理時間の比較

データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。

データ件数 N = 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
データ件数何件以上なら、クイックソートの方が高速になるか答えよ。

設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓が必要。

再帰呼び出しと再帰方程式

2019年5月7日

再帰関数と再帰方程式

// 階乗 (末尾再帰)
int fact( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x * fact( x-1 ) ;
}
// ピラミッド体積 (末尾再帰)
int pyra( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x*x + pyra( x-1 ) ;
}
// フィボナッチ数列 (非末尾再帰)
int fib( int x ) {
   if ( x <= 2 )
      return 1 ;
   else
      return fib( x-1 ) + fib( x-2 ) ;
}

これらの関数の結果について考えるとともに、この計算の処理時間を説明する。最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、 ${T(1)}=T_a$ で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理に加え、x-1の値で再帰の処理時間がかかる。このことから、 ${T(N)}=T_b+T(N-1)$ で表せる。

${T(1)}=T_a$
${T(N)}=T_b+T(N-1)$ } 再帰方程式

このような再帰を使って表した式は再帰方程式と呼ばれる。これを代入によって解けば、一般式 ${T(N)}=T_a-T_b+N T_b$ が得られる。

fact() や pyra() のような関数は、プログラムの末端に再帰が行われている。(fib()は、再帰の一方が末尾ではない)
このような再帰は、末尾再帰と呼ばれ、関数呼び出しの return を、再帰処理の先頭への goto 文に最適化が可能である。つまり繰り返し処理に書き換えが可能である。このため、ループにすれば局所変数を消費しない。

再帰を含む一般的なプログラム例

ここまでの再帰方程式は、再帰の度にNの値が1減るものばかりであった。もう少し一般的なプログラムで再帰方程式を使って処理時間を考えてみよう。
以下のプログラムを実行したらどんな値になるであろうか？それを踏まえ、処理時間はどのように表現できるであろうか？

int array[ 8 ] = {
  3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
} ;

int sum( int a[] , int L , int R ) { // 非末尾再帰
    if ( R - L == 1 ) {
        return a[ L ] ;
    } else {
        int M = (L + R) / 2 ;
        return sum( a , L , M ) + sum( a , M , R ) ;
    }
}
int main() {
    printf( "%d¥n" , sum( array , 0 , 8 ) ) ;
    return 0 ;
}

このような、処理を分割し、分割した処理を再帰で計算し、その分割した処理結果を組み合わせて結果を求めるような処理方法を、分割統治法と呼ぶ。

このことから、以下の再帰方程式が得られる。

${T_s(1)=T_{\alpha}}$

${T_s(N)=T_{\beta}+2\times{T_s(\frac{N}{2})}}$

これを、代入法により解いていくと、

${T_s(1)=T_{\alpha}}$

${T_s(2)=T_{\beta}+2\times T_{\alpha}}$

${T_s(4)=T_{\beta}+2\times T_s(2) = 3\times T_{\beta}+4\times T_{\alpha}}$

${T_s(N)=(N-1) T_{\beta} + N T_{\alpha} = -T_{\beta} + N(T_{\alpha}+T_{\beta})}$

ということで、このプログラムの処理時間は、 ${O(N)}$ で表される。

最後に、再帰方程式の事例として、ハノイの塔の処理時間について説明し、数学的帰納法での証明を示す。

ハノイの塔

ハノイの塔は、３本の塔にN枚のディスクを積み、ディスクの上により大きいディスクを積まずに、移動させるパズル。

一般解の予想

ハノイの塔の移動回数を ${H(N)}$ とした場合、少ない枚数での回数の考察から、 ${H(N)}=2^N-1$ … ① ということが予想ができる。
この予想が常に正しいことを証明するために、ハノイの塔の処理を、最も下のディスク1枚と、その上の(N-1)枚のディスクに分けて考える。

再帰方程式

上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、

${H(1)}=1$ … ②
${H(N)}=1+2H(N-1)$ 　… ③

ということが言える。(ハノイの塔の移動回数の再帰方程式)
ディスクが ${k=1}$ 枚の時、予想が正しいのは明らか①,②。
ディスクが ${k}$ 枚で、予想が正しいと仮定すると、 ${k+1}$ 枚では、

${H(k+1)}=1+2H(k)$ 　… ③
${H(k+1)}=1+2(2^k-1)$ … ①
${H(k+1)}=2^{k+1}-1$

となり、 ${k+1}$ 枚でも、予想が正しいことが証明された。よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

理解度確認

前再帰の「ピラミッドの体積」pyra() を、ループにより計算するプログラムを記述せよ。
前講義での2分探索法のプログラムを、再帰によって記述せよ。(以下のプログラムを参考に)
再帰のフィボナッチ関数 fib() の処理時間にふさわしい再帰方程式を示せ

int a[ 10 ] = {
   7 , 12 , 22 , 34 , 41 , 56 , 62 , 78 , 81 , 98
} ;
int find( int array[] , int L , int R , int key ) { // 末尾再帰
   // 目的のデータが見つかったら 1,見つからなかったら 0 を返す。
   if ( __________ ) {
      return ____ ; // 見つからなかった
   } else {
      int M = _________ ;
      if ( array[ M ] == key )
         return ____ ;
      else if ( array[ M ] > key )
         return find( array , ___ , ___ , key ) ;
      else
         return find( _____ , ___ , ___ , ___ ) ;
   }
}
int main() {
   if ( find( a , 0 , 10 , 56 ) )
      printf( "みつけた¥n" ) ;
}

タグアーカイブ: 再帰方程式

リンク集

検索・リンク

再帰呼び出しの基本

再帰呼び出しの処理時間

再帰を含む一般的なプログラム例

ハノイの塔

一般解の予想

再帰方程式

ハノイの塔

再帰方程式

理解度確認

再帰を使ったソートアルゴリズムの分析

マージソートの分析

選択法とクイックソートの処理時間の比較

前回の授業の復習と練習問題

練習問題

再帰呼び出しの基本

再帰呼び出しの処理時間

再帰を含む一般的なプログラム例

再帰関数と再帰方程式

再帰を含む一般的なプログラム例

ハノイの塔

再帰方程式

理解度確認

再帰を使ったソートアルゴリズム

マージソートの分析

選択法とクイックソートの処理時間の比較

解答

pyraをループで

2分探索法を再帰で

fib()の再帰方程式

再帰関数と再帰方程式

再帰を含む一般的なプログラム例

ハノイの塔

再帰方程式

理解度確認

再帰を使ったソートアルゴリズム

マージソートの分析

選択法とクイックソートの処理時間の比較

再帰関数と再帰方程式

再帰を含む一般的なプログラム例

ハノイの塔

再帰方程式

理解度確認

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー

メタ情報