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

解答

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の処理を行う。このため、以下の様な再帰方程式の細小時での処理時間は、

  … ①

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

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

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

  … ②

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

  … ③

となる。ただ、処理時間の見積もりでは厳密な分析が求められないので、(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(N)=fib(N-2)×T_b+fib(N+1)×T_a かな？よって、再帰のfib()の処理時間は、フィボナッチ数に比例する。ちなみに、フィボナッチ数はピネの公式で一般項が示されているので、処理時間のオーダーは、次式となる。