20100823 递归问题示例 for CS106B
一 函数递归
1 fibonacci数列 0 1 1 2 3 5 8 13 21 34 55 89 144
int Fib(int n)
{
if( n < 2 )
{
return n
}
else
{
return Fib(n-1) + Fib(n-2);
}
}
2 Power Example
1)base^exp = base*base^(exp-1)
int Raise(int base, int exp)
{
if(exp == 0)
{
return 1;
}
else
return base = Raise(base, exp-1);
}
2)base^exp = base^(exp/2)*base^(exp/2)
int Raise(int base, int exp)
{
if(exp == 0)
return 1;
else
{
int half = Rasie(base, exp/2);
if(exp%2 == 0)
return half = half;
else
retrun half = half * half;
}
}
3 Palindromes 回文数
bool IsPalindrome(string s)
{
if(s.length() <= 1) return true;
return s[0] == s[s.length()-1] && IsPalindrome(s.substr(1, s.length()-2);
}
4 Binary Search
int BSearch(Vector&V, int start, int stop, string key)
{
if(start > stop) return NotFound;
int mid = (start + stop)/2;
if(key == v[mid])
return mid;
else if (key < v[mid])
retrun BSearch(v, start, mid-1, key);
else
return BSearch(v, mid+1, stop, key);
}
5 Choose a subset
int C(int n, int k)
{
if(k == 0 || k == n)
return 1;
else
return C(n-1,k) + C(n-1,k-1);
}
二 过程递归
1 A familiar fractal
void DrawFractal (double x, double y, double w,double h)
{
DrawTriangle(x, y, w, h);
if(w < .2 || h < .2 ) return;
double halfH = h/2;
double halfW = w/2;
DrawFractal(x, y, halfW, halfH);
DrawFractal(x + halfW/2, y + halfH, halfW, halfH);
DrawFractal(x + halW, y, halfW, halfH);
}
2 Mondrian 蒙德里安（刚在hustle里看到this painting）
void DrawMondrian(double x, double y, double w, double h)
{
if(w <1 || h<1 )return;
FillRectangle(x, y, w, h，RandomColor());
switch (RendomInterger(0,2))
{
case 0:
break; //do nothing
case 1: //bisect vertically
double mixX = RandomReal(0,w);
DrawBlackLine(x+midX, y, h);
DrawMondrain(x, y, midX, h);
DrawMondrain(x+midX, y, w-midX, h);
break;
case 2: //bisect horizontally
double midY = RandomReal(0,h);
DrawBlackLine(x,y+midY,w);
DrawMondrain(x,y,w,midY);
DrawMondrain(x,y+midY,w,h-midY);
break;
}
}
3 Tower 汉诺塔
void MoveTover(int n, char src, char dst, char tmp)
{
if( n>0 )
{
MoveTower(n-1, src, tmp ,dst);
MoveSingleDisk(src ,dst);
MoveTower(n-1, tmp, dst, src);
}
}
4 Permutations 置换
void RecPermute(string sofar, string rest)
{
if(rest == "")
{
cout << sofar <
}
else
{
for(int i = 0 ; i < rest.length(); i++)
{
string next = sofar + rest[i];
string remaining = rest.substr(0,i) + rest.substr(i+1);
RecPermute(next, remaining);
}
}
}
5 Subset
void RecSubsets(string sofar, string rest)
{
if(rest == "")
count << sofar << endl;
else
{
// add to subset , remove from rest, recur
RecSubsets(sofar+rest[0],rest.substr(1));
// don't add subset ,remover from rest, recur
RecSubsets(sofar, rest.substr(1));
}
}
阅读(877) | 评论(0) | 转发(0) |
