|
Java将递归转换成循环+栈实现
1.命题：任何递归程序都可以转换成循环+栈实现。
这个命题之所以成立，是因为，在计算机底层。递归就是用栈实现的。
2.示例1：请用上述两种方式计算1到n的和。
2.1代码
TestRecursive 类【直接使用递归方法】
package InAction;
public class TestRecursive {
public static int calculate(int n){
if(n!=1)
return n+ calculate(n-1);
else
return 1;
}
}
TranformRecursiveToCirculation类【将递归转换成循环的实现】
package InAction;
import java.util.Stack;
public class TranformRecursiveToCirculation {
/*
1.实现1到n的累计求和
*/
public static int tranformRecursiveToCirculation(int n){
Stack stack = new Stack();
for(int i = n;i>= 1;i--){
stack.push(i);
}
int sum = 0;
while(!stack.empty()){
sum += stack.pop();
}
return sum;
}
}
可能有人会说，你拿这么简单的例子出来，不是忽悠我们吧。真的不是这样，我们可以通过这个例子，懂得大多数的递归的底部实现细节。
2.2分析
先看TestRecursive类 这里面一层层的递归将整数n压进栈中，直到整数为1时，才开始计算。也就是，n入栈，n-1入栈….2入栈，到1的时候，返回1。但是这个时候的调用却是2+calculate(2 - 1)。但是calculate(2-1)返回的是1。所以能够清楚的是，这个递归就是先计算1，再计算2+(1)，再计算3+(2+1)，最后到n+(n-1+(..+1))。 所以相同的用栈实现和循环实现，就是先入栈，然后将入栈元素出栈，依次累加即可。代码见上TranformRecursiveToCirculation类。
3.示例2.二分法使用递归、循环解决
public static int rankByCircle(int key, int[] a)
{ // 数组必须是有序的
int lo = 0;
int hi = a.length - 1;
while (lo a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
public static int rankByRecursive(int low,int high,int key,int [] a){
while(low key) {
rankByRecursive(low, mid - 1, key, a);
}
else
rankByRecursive(mid + 1, high, key, a);
}
return -1;
}
|