递归函数由操作系统的“系统栈”来实现，在调用另一函数前，操作系统先要：
1、下一条语句的地址入栈，即返回地址入栈：
2、被调用函数的形式参数 入栈，
3、被调用函数的局部变量 入栈
函数在声明或定义处的参数，称为形参，它实际上位于栈内的某个内存地址。至于实参，就是调用时函数时所用的参数，它不在栈内存区里。
当函数采用传值方式时，即把实在参数在栈中拷贝一份，用作形式参数；当函数采用传址方式时，即把实在参数的地址作为形式参数入栈；当有多个参数时，是参数a还是参数b先入栈，这依编译器而定，大都数编译器采用“从右到左的次序”将参数一个个压入。
当本次函数调用结束后：
1、保存函数返回值 （至通用寄存器EAX中）。
2、清理堆栈：先将局部变量出栈，再将形式参数出栈。至于由调用函数或被调用函数执行，参见调用约定
3、依据保存的返回地址将控制转移到调用函数。
//运用递归和二分查找特定整数在整型数组中的位置
public static int binarysearch1(int[] array,int index,int beginindex,int endindex){
int midindex=(beginindex+endindex)/2;
if(index<array[beginindex]||index>array[endindex]||beginindex>endindex)
return -1;
if(index<array[midindex]){
return binarysearch1(array,index,beginindex,midindex-1);
}else if(index>array[midindex]){
return binarysearch1(array,index,midindex+1,endindex);
}else{
return midindex;
}
}
//运用非递归和二分查找特定整数在整型数组中的位置
public static int binarysearch2(int[] array,int index){
int beginindex=0;
int endindex=array.length-1;
int midindex=-1;
if(index<array[beginindex]||index>array[endindex]||beginindex>endindex)
return -1;
while(beginindex<=endindex){
midindex=(beginindex+endindex)/2;
if(index<array[midindex]){
endindex=midindex-1;
}else if(index>array[midindex]){
beginindex=midindex+1;
}else{
return midindex;
}
}
return -1;
}
以上两种方式都可以解决在数组中元素所在位置的搜索；
只是：递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。
|
|
收藏
淘帖
踩
