Document

再帰
データ構造とプログラミング（８）
大岩元
慶応大学環境情報学部
[email protected]
再帰の例（三角数）
再帰公式
triangle(n) = n + triangle(n-1)
triangle(1) = 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 の終り

Download Report