大岩 元 慶応大学環境情報学部 ohiwa@sfc.keio.ac.jp 再帰 データ構造とプログラミング（８） 大岩 元 慶応大学環境情報学部 ohiwa@sfc.keio.ac.jp
再帰の例（三角数） 再帰公式 一般公式 プログラム triangle(n) = n + triangle(n-1) triangle(n) = (n*n + n)/2 プログラム int triangle {if(n==1) return 1 else return(n + triangle(n-1))}
再帰の例（階乗） 再帰公式 プログラム n! = n*(n-1)! 0! = 1 int factorial(n) {if(n==0) return 1 else return( n*factorial(n-1)}
アナグラム 文字列に含まれる文字から形成される同じ長さの文字列 ｎ文字から成る文字列の、全てのアナグラムを求めるには 右側の n-1 文字の全てのアナグラムを求める ｎ文字の文字列全体を１文字分回転する 以上をｎ回繰り返す
二分探索 int find(double searchKey) {int lowerBound = 0; int upperBound = nElems -1; int curIn; while(true) { curIn = (lowerBound + upperBound)/2; if(a[curIn] == searchKey) return curIn;// 見つかった else if (lowerBound > upperBound) return nElms; // 見つからず else {if (a[curIn] < searchKey) lowerBound = curIn + 1; // 上半分を探索 else upperBound = curIn -1; // 下半分を探索 } // 範囲分割の終り } // while の終り } // find（）の終り
再帰による二分探索 int find(double searchKey, int lowerBound, int upperBound) { int curIn; curIn = (lowerBound + upperBound)/2; if(a[curIn]==searchKey) return curIn; // 見つかった else if(lowerBound > upperBound) return nElems; // 見つからない else // 範囲を半分にする {if (a[curIn] < searchKey) // 上半分を調べる return recfind(searchKey, curIn+1, upperbound); else // 下半分を調べる return recfind(searchKey, lowerBound, curIn-1); } // 範囲分割の終り } // recfind の終り