递归与分治题目

递归问题
例1 Fibonacci数列

int fibonacci(int n){      
if (n <= 1) return 1;     
return fibonacci(n-1)+fibonacci(n-2);
}

例2 汉诺塔问题（移动路径）

void move(char from ,char to) {
cout<<“Move “<<from<<“to”<<to<<endl；
 }
void hanoi(int n, char first, char
second,  char third) {        
if(n==1)     
move(first,third);    
else{      
hanoi(n-1,first,third,second);        尤为注意实参和形参的对应关系
move(first,third);       
hanoi(n-1,second,first,third);     
}
 }

实例化
int main(){   
int m;
cout<<“the number of diskes:";   
cin>>m;  
cout<<"move 
“<<m<<“ 
diskes:\n";   
hanoi(m,'A','B','C');
}




结果：

the number of diskes:3
move 3  diskes:
Move A to  C
Move A to  B
Move C to  B
Move A to  C
Move B to  A
Move B to  C
Move A to  C
Press any key to continue

例3 猴子吃桃
猴子第一天采摘了一些桃子，第二天吃了第一天的一半多一个，第三天吃了第二天的一半多一个…直到第十天就剩下一个。问：猴子第一天摘了多少桃子？

 #include <iostream>
 using namespace std;
 int func(int day){
     if(day==10)
         return 1;                                                  //终止条件很重要
     else
         return (func(day+1)+1)*2;         //找到依赖关系很重要
 }
 int main(){
     cout<<"第一天有%d个桃子！"<<func(1)<<endl;
     return 0;
 }

例4 进制转换
编写一个递归函数，将10进制转化成radix进制（输出二进制形式）