文章目录

  递归是经典的算法思想,递归的代码优美而简洁易懂。系统在处理递归时,使用系统调用栈来保存递归调用点的内存地址,以保证在返回时能够回到上一层方法的调用点继续执行。本文通过利用栈数据结构将一个简单的递归方法改写为为使用循环的方法,模拟了系统调用栈在处理递归时的行为。理解系统调用栈的行为,有助于我们对递归有更加深刻的理解。
  下面给出递归方法的代码和改写后的代码:

  • 递归方法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package systemStack;
/**
* Created by wuwenan on 25/06/2017.
*/
public class Recursion {
private static int Foo(int n){
if(n<=1){
return 1;
}else{
return n*Foo(n-1);
}
}
public static void main(String[] args) {
System.out.println(Foo(10));
}
}

  这是一个简单的递归方法,其中递归的部分为f(n)=n*f(n-1),下面将该方法改写为使用循环的方法。递归的调用分为两个阶段,第一阶段为call阶段,是从上层向下层一层层调用的阶段;第二阶段为return阶段,是从递归边界开始从下层想上层一层层返回的阶段。

  • 改写后的循环方法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package systemStack;
import java.util.Stack;
/**
* java模拟递归调用的系统栈
* Created by wuwenan on 25/06/2017.
*/
public class SystemStack {
private static int Foo(int n){
//使用栈模拟系统栈的行为
Stack<Integer> systemStack = new Stack<>();
//back为true,表示递归调用的返回过程;back若为false,表示递归调用的调用过程
boolean back = false;
int result=0;
do{
if(!back){
//调用过程
if(n<=1){
back = true;
result = 1;
}
systemStack.push(n);
n--;
}else{
//返回过程
result*=systemStack.pop();
}
}while(!systemStack.isEmpty());
return result;
}
public static void main(String[] args) {
System.out.println(Foo(10));
}
}

  上面的代码中使用了栈的数据结构模拟了系统调用栈的过程。这段代码有以下几个注意点:

  • 使用boolean类型变量back标识递归的调用和返回过程,若back值为true,表示当前的过程为return过程;若back值为false,表示当前过程为call过程。
  • 在call过程中将每一层使用到的n值放入栈中
  • 在return过程中将栈中的值一个个取出以和之前一次执行的结果相乘。
  • 递归的边界是n<=1

      两段代码输出的结果均为:

1
3628800
文章目录