递归

一.递归：镜子

 递归的惊人之处：这些小的问题与初始问题的类型完全相同，即所谓的镜像

  递归的解决方案：

      。怎样按照同类型的更小问题来定义问题

      。各个递归的调用怎样减小问题的规模

      。哪个问题的实例可以做基例

      。随着问题的规模的减小，最终能否达到基例

举例：

递归值方法：n的阶乘

                         1    n=0

  递归定义：factorial(n)={

                         n*factorial(n-1) n>0 

 

 

public static int factorial(int n){
if(n=0){

return 1;

}else{
return n*factorial(n-1);
}
}

递归void方法：逆置字符串                                      

解决方案：先输出最后一个字符，在逆置其余的字符

递归的定义：writeBackWord(string,size)=输出最后一个字符串 size>0

public static void writeBackword(String s,int size){
if(size>0){
System.out.println(s.substring(size-1,size));
writeBackWord(s,size-1);
}
}

 

折半查找：首先要对数组进行排序

伪代码：

binarySearch(anArray,value){
if(anArray is of size 1){
Detemine if anArary's item is equal to vlaue

}else{

Find the modpoint of anArray

Detemine which half of anArray contains value

if(value is in the first half of anArray){

biarySeach(the first half of anArry,value);

}else{

biarySearch(second half of anArary,value);

}

}

代码：

public static int binarySearch(int anArray[],int first,int last,int value){
int index;
if(first>last){
index=-1;
}else{
int mid=(first+last)/2
if(value==anArray[mid]){
index=mid;
}else if(value<anArray[mid]){
index=binatySearch(anArray,first,mid-1,value);
}else{
index=bianrySearch(anArray,mid+1,last,value);
}
}
}

Hanoi塔问题：

解决思路：首先将A最上面的n-1快移动到C上，然后把A上的左后一个盘移动到B上，最后在把C上的盘子移动到B上！

public static void solveTowers(int count,char sourcechar destination,char spare){
if(count==1){
System.out.println("Move top disk from pole"+source+"to pole"+destination);
}else{
solveTowers(count-1,source,spare,destination);
soleTowers(1,source,destination,spare);
soleTowers(count-1,spare,destination,source)
}
}

数据抽象：墙

ADT并不是数据结构的别名：

  ADT是指数据集合和针对这些数据的一组操作

  数据结构是编程语言中用于存储数据的一种结构