学习递归

关于递归

说到递归，其实已经接触了很久了。但是却一直没有真正地学会用他。今天想在学二叉树之前好好整理一下自己关于递归的认识。

Eric Lippert在stackoverflow上

Svick’s solution is fine, but I thought I’d add a bit more general advice. It seems like you are new to writing recursive methods and were struggling a bit there. The easiest way to write a recursive method is to strictly follow a pattern:(书写递归的方法，需要严格按照这个模式。)

Result M(Problem prob)
{
    if (<problem can be solved easily>)
        return <easy solution>;
    // The problem cannot be solved easily.
    Problem smaller1 = <reduce problem to smaller problem>
    Result result1 = M(smaller1);
    Problem smaller2 = <reduce problem to smaller problem>
    Result result2 = M(smaller2);
    ...
    Result finalResult = <combine all results of smaller problem to solve large problem>
    return finalResult;
}

So suppose you want to solve the problem “what is the maximum depth of my binary tree?”（尝试用该模式写一个方法求二叉树的深度）

int Depth(Tree tree)
{
    // Start with the trivial case. Is the tree empty?
    if (tree.IsEmpty) return 0;
    // The tree is not empty. 
    // Reduce the problem to two smaller problems and solve them:
    int depthLeft = Depth(tree.Left);
    int depthRight = Depth(tree.Right);
    // Now combine the two solutions to solve the larger problem.
    return Math.Max(depthLeft, depthRight) + 1;
}

You need three things to make recursion work:（使用递归必须确保三件事）

The problem has to get smaller every time you recurse.
The problem has to eventually get so small that it can be solved without recursion
The problem has to be solvable by breaking it down into a series of smaller problems, solving each one, and combining the results.
If you cannot guarantee those three things then do not use a recursive solution.

我对递归的认识

之前学递归的时候，首先明白递归就是把一个复杂问题化为一系列简单问题的重复，然后：

• 递归就是个循环，递归内容就是循环体内容，递归内容包括循环体的判断条件
• 递归与堆栈紧密相连

递归程序一般都可以用循环来代替解决。递归深度不确定，使得堆栈会出现溢出，如果是递归时候堆栈爆了，那么我们程序员是无法处理的，因为这时候的堆栈是OS分配管理的，而如果是我们用循环实现，就会自己管理一个堆栈，出现溢出我们也可以自己在程序中解决。循环的效率更高；递归使得程序更简洁。

刚才自己尝试了一下，不知不觉验证了Eric Lippert提出的模式

public class Test {
	
	/**
	 * 与循环过程相反；如要从i=1开始打印输出，我们要注意的是因为递归利用的是堆栈的存储结构，
	 * 那么就会"后进先出"，那么在初始化第一个形参的时候，所传值是在最后一个栈帧弹出时恢复。
	 * @param i 其中一个压入栈的值
	 * @return 弹出一个栈帧内容，恢复上次执行状态。
	 */
	public  static int printIndex(int i){//形参作用：循环中的初始化，
		
		if(i==1) return i;//递归出口，循环中的判断。i局部变量会出现在第一个从堆栈弹出的栈帧中。
		
		int nextIndex = printIndex(i-1);//nextIndex的值，第一次一定是递归出口返回的值。存放上一个返回的值。
		
		System.out.println(nextIndex);//循环体
		
		return  i;//弹出栈帧，并返回该值给调用者
	}
	
	public static void main(String[] args) {
		
		System.out.println(Test.printIndex(6));//之所以不打印6，是因为返回6给main的时候，没有输出。
				
	}
}

//上一个的改进，充分利用堆栈来设计递归程序。
public class Test {
	
	public  static int printIndex(int i){
		if(i==1){
			System.out.println(i);
			return i+1;
		}
		int x = printIndex(i-1);
		System.out.println(x);
		return i+1;
	}
	
	public static void main(String[] args) {
		Test.printIndex(5);
	}
}

总结一下，其实递归和循环差不多，只是递归会运用到堆栈来存储数据（所以会有出栈入栈操作），而这也是递归比循环差的地方，就是空间消耗大，系统给的堆栈一般不会很大，解决办法是我们自定义一个大空间的堆栈，或者动态增长的链表堆栈，这样就解决了爆栈的问题，虽然跟循环比起来还是空间大了很多。