java 递归深入理解

一、递归函数，通俗的说就是函数本身自己调用自己...

如:n!=n(n-1)!
你定义函数f(n)=nf(n-1)

而f(n-1)又是这个定义的函数。。这就是递归

二、为什么要用递归：递归的目的是简化程序设计，使程序易读

三、递归的弊端：虽然非递归函数效率高，但较难编程，可读性较差。递归函数的缺点是增加了系统开销，也就是说，每递归一次，栈内存就多占用一截

四、递归的条件：需有完成任务的语句，需满足递归的要求(减小而不是发散)

五、递归进阶：
1.用递归算n的阶乘：

分析：n!=n*(n-1)*(n-2)...*1

 public int dReturn(int n){
   if(n==1){
    return 1;
   }else{
    return n*dReturn(n-1);
   }
  } 

2.用递归函数算出1到n的累加：1+2+3+4+..+n

 public int dReturn(int n){
  if(n==1){
   return 1;
  }else{
   return n+dReturn(n-1);
  }
 } 

3.要求输出一个序列：1,1,2,3,5,8,11......（每一个数为前两个数子之和，要求用递归函数）
  用java递归来表示一个函数:F(n)=F(n-1)+F(n-2);F(0)=1;F(1)=1;
   分析：X1=1; X2=1; X3=X1+X2; X4=X2+X3; ... ; Xn=X(n-1)+X(n-2)

  public int F(int n){
  if(n==1){
   return 1;
  }else if(n==2){
   return 1;
  }else{
    return F(n-1)+F(n-2);
  }
 } 

4.java用递归方法反向打印一个整数数组中的各个元素

  public static void printAll(int index,int[] arr){
   System.out.println(arr[index]);
   if(index > 0){
    printAll(--index,arr);
   }
  }
  public static void main(String[] args){
   int[] arr={1,2,3,4,5};
   printAll(arr.lenth-1,arr);
  } 

5.编程求解：若一头小母牛，从出生起第四个年头开始每年生一头母牛，按次规律，第 n 年时有多少头母牛？

  public static int cattle(int n){
if(n<=0){
 return 0;
}else if(n<=3){
 return 1;
}else{
 return cattle(n-1)+cattle(n-3);
}
  }
  public static void main(String[] args){
   int n=10;
   System.out.println(n+"年后共有"+cattle(n)+"头牛");
  } 

递归、线性递归、尾递归的概念？

Java中递归函数的调用-求一个数的阶乘

不考虑溢出：一般只能算到69的阶乘……

注意：0的阶乘0！=1

任何大于1的自然数n阶乘表示方法：
n!=1×2×3×……×n
或n!=n×(n-1)!
搜索0的阶乘，可以出来一个在线计算器，很实用哦！！

package test;

import java.util.Scanner;

public class DiGui {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println("输入一个整数：");
		Scanner scan = new Scanner(System.in);
		int x = scan.nextInt();
		int result = digui(x);
		System.out.println(result);
	}

	//递归函数
	public static int digui(int x){
		if(x<=0){
			return 1;
		}else{
			return x*digui(x-1);
		}
	}
}

递归：一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。本案例很清楚的说明了递归是如何将一个复杂的问题转化为规模较小的问题来解决的。下面通过一个小例子来说明递归的原理。

/**
* @fileName Test.java
* @description ??????????
* @date 2012-11-25
* @time 17:30
* @author wst
*/
public class Test {
  static int multiply(int n) {
    int factorial; // ?? 

    if ((n == 1) || (n == 0)) {
      factorial = n;
    } else {
      factorial = n * multiply(n - 1);
    }

    return factorial;
  }

  public static void main(String[] args) {
    System.out.println(multiply(5));
  }
}

当函数被调用时，它的变量的空间是创建于运行时堆栈上的。以前调用的函数的变量扔保留在堆栈上，但他们被新函数的变量所掩盖，因此 是不能被访问的。
程序中的函数有两个变量：参数n和局部变量factorial。下面的一些图显示了堆栈的状态，当前可以访问的变量位于栈顶。所有其他调用的变量饰以灰色的阴影，表示他们不能被当前正在执行的函数访问。
假定我们以5这个值调用递归函数。堆栈的内容如下，栈顶位于最下方：

n multiply(n) factorial
5 multiply(5) 5*multiply(4) //第一次调用
4 multiply(4) 4*multiply(3) //第二次调用
3 multiply(3) 3*multiply(2) //第三次调用
2 multiply(2) 2*multiply(1) //第四次调用
1 multiply(1) 1 //第五次调用 

从上面的信息可以很容易的看出，递归是如何将一个问题逐渐最小化来解决的，从方法调用开始，factorial结果都会被压入栈，直到方法调用结束，最后从栈顶逐个返回得到结果。经过逐个代入，结果如下:
n=1 1 向上返回 1
n=2 2*multiply(1) 向上返回 2*1=2
n=3 3*multiply(2) 向上返回 3*(2*1)=6
n=4 4*multiply(3) 向上返回 4*(3*(2*1))=24
n=5 5*multiply(4) 向上返回 5*(4*(3*(2*1)))=120
注意：因为multiply(1)或multiply(0)返回的值为1
所以就有 2*multiply(1)=2*1=2
又因为multiply(2)符合递归条件，递归后可化为2*multiply(1)
所以就有3*multiply(2)=3*(2*multiply(1))=3*(2*1)=6
因为multiply(3)递归后可化为3*multiply(2)
所以multiply(4)=4*multiply(3)=4*(3*multiply(2))=4*(3*(2*1))=24
以此类推，multiply(5)=5*multiply(4)
可化为5*(4*multiply(3))=5*(4*3*(multiply(2)))=5*(4*(3*(2*1)))=120
再来看看字节码信息:

public class Test extends java.lang.Object{
public Test();
Code:
0: aload_0
1: invokespecial #1; //Method java/lang/Object."<init>":()V
4: return
static int multiply(int);
Code:
0: iload_0
1: iconst_1 //将int类型常量1压入栈
2: if_icmpeq 9 //将两个int类型值进行比较，相等，则跳转到位置9，这就是||的短路功能
5: iload_0 //此处是在第一个条件不成立的情况下执行，从局部变量0中装载int类型值（将n的值压入栈）
6: ifne 14 //比较，如果不等于0则跳转到位置14，注意：由于此处默认和0比较，所以没有必要再将常量0压入栈
9: iload_0 //如果在ifne处没有跳转，则从局部变量0中装载int类型值（将n的值压入栈）
10: istore_1 //将int类型值存入局部变量1中（弹出栈顶的值即局部变量0压入栈的值，再存入局部变量1中）
11: goto 23 //无条件跳转至位置23
14: iload_0 //位置6处的比较，如果不等于0执行此指令，从局部变量0中装载int类型值（将n的值压入栈）
15: iload_0 //从局部变量0中装载int类型值（将n的值压入栈）
16: iconst_1 //将int类型常量1压入栈，常量1是代码中n-1的1
17: isub //执行减法操作，n-1
18: invokestatic #2; //Method multiply:(I)I，调用方法multiply
21: imul //执行乘法操作，n * multiply(n - 1)
22: istore_1 //将int类型值存入局部变量1中，factorial=...
23: iload_1 //从局部变量1中装载int类型值（将factorial的结果压入栈）
24: ireturn //方法返回
public static void main(java.lang.String[]);
Code:
0: getstatic #3; //Field java/lang/System.out:Ljava/io/PrintStream;
3: iconst_5
4: invokestatic #2; //Method multiply:(I)I
7: invokevirtual #4; //Method java/io/PrintStream.println:(I)V
10: return
}