关于递归和尾递归的原理

基础很重要，这是永远不变的真理。

package sunfa;

public class DiGui {
	public static void main(String[] args) {
		Stack<Integer> stack = new Stack<Integer>(5);
		for (int i = 0; i < 5; i++) {
			stack.push(i);
		}
		System.out.println("dg:");
		dg(stack);
		System.out.println("jc：");
		System.out.println(jc(10));
		System.gc();
		System.out.println("wjc：");
		int r = 1;
		System.out.println(wjc(10, r));
	}

	/*
	 * 要求：栈内的元素要求从栈底开始打印。
	 * 
	 * 递归编程涉及到栈，也就是说比如一个函数在执行的时候遇到了一个递归函数，那么它执行完了该递归函数后必须会执行递归函数后门的代码，
	 * 反过来说就是这个递归函数后面的代码必须在该递归函数执行完了后才能得到执行。
	 * 
	 * 原理：一个函数执行过程中遇到递归(可能是自己或别人的)，那么它后面的代码会进行入栈处理，如果这句入栈的代码是这个函数的
	 * 最后一句代码，那它肯定就只能最后被执行了。
	 * 
	 * 用途：比如并查集的路径压缩、平衡二叉树的系列的路径修复(下面的元素通过旋转往上升)都是基于递归的这个特点的。
	 */
	private static void dg(Stack<Integer> stack) {
		if (stack.count() > 0) {
			Object o = stack.poll();
			dg(stack);
			System.out.println(o);
		}
	}
	private static void fdg(Stack<Integer> stack) {
		while (stack.count() > 0) {
			Object o = stack.poll();
			dg(stack);
			System.out.println(o);
		}
	}
	/*
	 * 普通递归：
	 * jc(5)==>
	 * 5*jc(4)--->表达式入栈
	 * 5*4*jc(3)--->上一步的jc(4)是递归表达式，所以此处要先对其进行出栈，计算完jc(4)=4*jc(3)后在将表达式4*jc(3)入栈
	 * 5*4*3*jc(2)--->同上
	 * 5*4*3*2*jc(1)--->同上
	 * 5*4*3*2*jc(1)  ==>由于n=1的时候函数返回的是一个常数1，这个时候表达式变成5*4*3*2*1，不含有任何函数了，
	 * 所以开始计算该表达式的结果，计算结果的过程也是一个出栈并计算的过程。
	 */
	private static int jc(int n) {
		if (n == 1)
			return 1;
		return n * jc(n - 1);
	}

	/*
	 * 尾递归:
	 * wjc(5,1)==>
	 * wjc(4,5)
	 * wjc(3,20)
	 * wjc(2,60)
	 * wjc(1,120)
	 * 尾递归是把每一步的结果都计算好了，所以不存在表达式入栈的缺点。
	 * 
	 * 很明显，普通递归并没有计算每一步的结果，而是到最后一步才去计算的， 它的每一步都包含一个表达式，这个表达式
	 * 用栈来存放，当然栈顶的肯定是一个表达式，所以每一步生成的表达式入栈后到下一步的时候把栈顶的表达式出栈，并解该
	 * 表达式，一直如此直到栈内不存在函数，这个时候才开始计算，如果没有退出条件或因为栈已满了那就会栈溢出。
	 * 
	 */
	private static int wjc(int n, int r) {
		return n == 1 ? r : wjc(n - 1, r * n);
	}
}

评论

3 楼 a346063587 2011-10-26  

嗯。。的确，基础很重要！

2 楼 zhufeng1981 2011-10-26  

huoyj 写道

基础很重要，这是永远不变的真理。 很赞同这句话

很赞同。

1 楼 huoyj 2011-10-26  

基础很重要，这是永远不变的真理。 很赞同这句话