Java基础之递归调用的机制

public class Recursion {
	public static void main(String[] args) {
		T t = new T();
		t.test(4);  //输出n=2,n=3,n=4
		
		int res = t.factorial(4);
		System.out.println("4的阶乘等于" + res);
	}
}

class T {
	//打印问题
	public void test(int n) {
		if(n > 2) {
			test(n - 1);
		}
		System.out.println("n=" + n);
	}
	//阶乘问题
	public int factorial(int n) {
		if(n == 1) {
			return 1;
		} else {
			return factorial(n - 1) * n;
		}
	}
}

第一步，main栈中创建 t 对象，调用test(4)，开辟一个新的test栈
第二步，判断n=4 > 2成立，调用test(4 - 1)，开辟一个新的test栈
第三步，判断n=3 > 2成立，调用test(3 - 1)，开辟一个新的test栈
第四步，判断n=2 > 2不成立
第五步，继续向后执行System.out.println(“n=” + n)，输出n=2，然后返回到test(3 - 1)
第六步，继续向后执行System.out.println(“n=” + n)，输出n=3，然后返回到test(4 - 1)
第七步，继续向后执行System.out.println(“n=” + n)，输出n=4，然后返回到test(4)，main方法执行完毕，程序执行结束

第一步，main栈中创建 t 对象，调用f(4)，开辟一个新的factorial栈
第二步，判断n=4 ≠ 1，执行return f(4 - 1) * 4，开辟一个新的factorial栈
第三步，判断n=3 ≠ 1，执行return f(3 - 1) * 3，开辟一个新的factorial栈
第四步，判断n=2 ≠ 1，执行return f(2 - 1) * 2，开辟一个新的factorial栈
第五步，判断n=1 = 1，执行return 1，方法执行完毕，返回到f(2 -1)
第六步，执行1 * 2 = 2，方法执行完毕，返回到f(3 - 1)
第七步，执行2 * 3 = 6，方法执行完毕，返回到f(4 - 1)
第八步，执行6 * 4 = 24，方法执行完毕，返回到f(4)
第九步，继续执行System.out.println(“4的阶乘等于” + res)，输出4的阶乘等于24，main方法执行完毕，程序执行结束

细节说明：

每调用一次方法，就会创建一个新的受保护的独立栈空间当一个方法执行完毕或者执行到return语句时，就会返回到调用该方法的地方当方法执行完毕或者返回时，该方法也就执行完毕，同时会释放栈空间

public class HNTower {
	public static void main(String[] args) {
		Tower tower = new Tower();
		tower.HanoiTower(3, 'A', 'B', 'C');
	}
}

class Tower {
    //总共num个盘，要从a移到c，中间借助b
	public void HanoiTower(int num, char a, char b, char c) {
	    //如果只有一个盘，则直接从a移到c
		if(num == 1) {
			System.out.println(a + "->" + c);
		} else {
		    //如果有多个盘，可看成两个盘，最下面一个和上面的所有
		    //先移动上面num-1个盘到b，借助c
			HanoiTower(num - 1, a, c, b);
			//再把最下面一个盘从a移到c
			System.out.println(a + "->" + c);
			//最后把b上的num-1个盘移到c，借助a
			HanoiTower(num - 1, b, a, c);
		}
	}
}