import java.util.Scanner;
//用递归的方法求n的阶乘
public class Re1 {

    public static void main(String args[]){
        Scanner input = new Scanner(System.in); //构建一个输入实例
        int n = input.nextInt();                //输入n的值
//    n的阶乘的值为：factorial(n);                //用递归函数求解n的阶乘
        System.out.println("The anwser of n! is " + factorial(n));
    }

    public static int factorial(int n){         //阶乘求解函数
        if(n == 0){                             //判断传进来的n是否为0，若为零返回阶乘为1
            return 1;
        }
        return n*factorial(n-1);             //重新调用函数，继续判断n-1是否为零，
    }                                          //若不为0则return值为n*(n-1)*factorial(n-1-1),直到n=0，跳出函数
}

            采用递归的方法创建二叉树，可以灵活地创建任意形态的二叉树，这里用先序递归举例，中序和后序同理。
 
           首先贴一下Node节点类，大同小异。     
 

public class Node {
	private int data;
	private Node lchild;
	private Node rchild;
	public int getData() {
		return data;
	}
	public void setData(int data) {
		this.data = data;
	}
	public Node getLchild() {
		return lchild;
	}
	public void setLchild(Node lchild) {
		this.lchild = lchild;
	}
	public Node getRchild() {
		return rchild;
	}
	public void setRchild(Node rchild) {
		this.rchild = rchild;
	}
	public Node(int data, Node lchild, Node rchild) {
		super();
		this.data = data;
		this.lchild = lchild;
		this.rchild = rchild;
	}
	@Override
	public String toString() {
		
		return "Node [data=" + data + ", lchild=" + lchild + ", rchild="
				+ rchild + "]";

	}
	

}
                
 
          下面是递归创建二叉树的方法，代码很简单，为了灵活创建树，用户需要输入每个节点的值，当输入的值为0时，认为这个节点为空。
 
           
public  Node CreateInRecur(Scanner scanner){
	 int data = scanner.nextInt();
	 if(data==0)                     //输入data为0时，认为该节点为空节点
		 return null;
     Node node =new Node(data,CreateInRecur(scanner),CreateInRecur(scanner));
     return node;
	}
         
 比如要生成下面这颗树：
 
       
 
        用户输入的节点data先后为： 1 2 0 4 0 0 3 5 0 0 0
 
        通过先序遍历打印的方式，得到各个节点的toString如下，说明已经成功创建了树：
 
         
Node [data=1, lchild=Node [data=2, lchild=null, rchild=Node [data=4, lchild=null, rchild=null]], rchild=Node [data=3, lchild=Node [data=5, lchild=null, rchild=null], rchild=null]]
Node [data=2, lchild=null, rchild=Node [data=4, lchild=null, rchild=null]]
Node [data=4, lchild=null, rchild=null]
Node [data=3, lchild=Node [data=5, lchild=null, rchild=null], rchild=null]
Node [data=5, lchild=null, rchild=null]
         
 个人觉得这种递归方式创建树很灵活，但是代价就是需要用户手动输入每个节点以决定树的形态。
              

 
文章目录
 
Java结合方法栈帧理解递归编程思想
递归的介绍
阶乘——递归入门案例
递归和方法栈
尾递归优化
汉诺塔实现
 

 
Java结合方法栈帧理解递归编程思想
 
递归的介绍
 
 
 
In computer programming, the term recursive describes a function or method that repeatedly calculates a smaller part of itself to arrive at the final result. It is similar to iteration, but instead of repeating a set of operations, a recursive function accomplishes repetition by referring to itself in its own definition. While the concept of recursive programming can be difficult to grasp initially, mastering it can be very useful. Recursion is one of the fundamental tools of computer science.
 
 
在计算机编程中，递归描述了一个函数或方法重复计算自身的更小部分单元，从而获得最终结果。有点类似于迭代，但不是重复一系列的普通操作，而是在自身定义里面重复调用自身完成。递归的概念确实比较难以理解，但是理解后是极其有用的。递归是计算机科学的工具之一。
 
上面是比较学术化的说法，关于递归，简而言之——函数（或者某些语言叫方法）体里面又调用了自身，从而得到最终的结果。
 
递归的注意事项
 
一定要保证递归终止的条件，否则会陷入无限调用的噩梦
每次递归，应该可以解决更小的子集问题
 
阶乘——递归入门案例
 
阶乘：是最好的递归案例。
 
0的阶乘=1; ----- 因为1!=1，根据1!=1*0!，所以0!=1而不是0。
 
1的阶乘=1;
 
2的阶乘=2*1!=2;
 
3的阶乘=3*2!=6;
 
4的阶乘=4*3!=24;
 
我们发现一个非负数的阶乘 = 其值*(其值-1)!
 
在编程，求一个给定数的阶时可以这么实现：
 
private int factorial(int i){
    if( i <= 1 ){
        return 1;
    }else{
        return i * factorial(i-1);
    }
}

 
结果验证…没毛病！
 
递归和方法栈
 
回顾一下：JMM内存模型。
 
 
对于上面代码：
 
private int factorial(int i){
    if( i <= 1 ){
        return 1;
    }else{
        return i * factorial(i-1);
    }
}
 
结合JMM模型来分析一下，每个方法调用时都有属于自己的栈帧； 所以每次调用时都会
 
①保存当前这次栈帧的局部变量
 
②操作，去继续调用比它小1的栈帧
 
③继续执行①-③，知道找到最后一个——递归终止条件return 1
 
④方法逐步返回，回到上一层的栈帧…直到最开始的栈帧，拿到结果，出栈。
 
这个过程需要大量栈帧，我们知道栈帧是需要一定的内存的，所以空间损耗很大；
 
尾递归优化
 
尾递归——当递归调用时最后的语句是函数自身，并且没有任何其他的表达式；
 
对于尾递归，现代编译器会对其做优化，复用栈帧。
 
改写，使用尾递归，复用栈帧：
 
private  int factorial2(int i, int result){
    if( i <= 1 ){
        return result;
    }else{
        return factorial2(i-1, i*result);
    }
}
 
最后的执行语句仅仅包含方法自身，则可以复用栈帧，只要一个栈帧即可。
 
汉诺塔实现
 
理解了递归思想后，来看一看当初数据结构课上的一个案例：汉诺塔。
 
 
对于初学者，这个案例看着很头疼…似乎陷入了无解的状态…
 
圆盘一开始全部像叠罗汉一样都在A，有空柱子B、C；
最终要求全部放到C盘；
盘移动过程中可以在任意柱子；
一次只能移动一个盘；
移动期间，需保证所有的柱子都是底层为大盘，上面的为小盘；
 
 
分析
 
这个问题如果存在解，那么应该是采用递归、循环来实现；
 
递归？ 如何递归？
 
如何拆分任务子集？
 
实现
 

 假设A上面存在2个圆盘——要原样移动到C，需要经历以下步骤；
 
A移动到B
 
 
A移动到C
 

 B移动到C
 
 
 
 
同样的N个，可以把下面的N-1整体看成一个，最上面一个，合起来算做两个；按上面的操作完成；
 
 
这就是不断地细分，每一块又是重复的动作，可以递归实现。
 
 
本质上就是一个入栈、出栈的过程
 
 
// 将 n 个圆盘从 a 经由 b 移动到 c 上
public void hanoid(int n, char a, char b, char c) {
    if (n <= 0) {
        return;
    }
    // 将上面的  n-1 个圆盘移到 B
    hanoid(n-1, a, c, b);
    // 此时将 A 底下的那块最大的圆盘移到 C
    move(a, c);
    // 再将 B 上的 n-1 个圆盘经由A移到 C上
    hanoid(n-1, b, a, c);
}

public void move(char a, char b) {
    printf("%c->%c\n", a, b);
}