什么是递归函数

    递归函数即自调用函数，在函数体内部直接或间接地自己调用自己，即函数的嵌套调用是函数本身。 

实例分析

    后一个数是前两个数之和，求第40个数

public class Fab2 {	public static void main(String arg[]) {		System.out.println(f(40));	}		public static int f(int n){		if(n==1 || n==2){			return 1;		} else {			return f(n-1) + f(n-2);		}	}}

    运行结果：

    下面介绍一下该函数的调用过程，为了简单起见，以求f(5)为例

     非递归函数实现上述功能

public class Fab{	public static void main(String[] args){		System.out.println(f(5));	}			public static long f(int index){		if (index < 1){			System.out.println("wrrong");			return -1;		}				if (index == 1 || index == 2){			return 1;		}				long f1 = 1;		long f2 = 1;		long f = 0;				for (int i = 0; i <index-2; i++){			f = f1 + f2;			f1 = f2;			f2 = f;				}		return f;	}}

递归函数的特点

    （1）原始问题转化成解决方法相同的新问题

    （2）新问题的规模比原始问题小

    （3）新问题又可以转化为解决方法相同的规模更小的新问题，直接至终止条件为止

递归函数条件

    （1）存在递归结束条件及结束时的值

    （2）能用递归形式表示，且递归向终止条件发展

递归反映的思维

    即大事化小，小事化了。

递归函数与非递归函数的比较

    （1）递归的目的是简化程序设计，使程序易读。   

    但递归增加了系统开销。 时间上， 执行调用与返回的额外工作要占用CPU时间。空间上，随着每递归一次，栈

内存就多占用一截。   

  　（2）相应的非递归函数虽然效率高，但却比较难编程，而且相对来说可读性差。   

  　现代程序设计的目标主要是可读性好。随着计算机硬件性能的不断提高，程序在更多的场合优先考虑可读而不是

高效，所以，鼓励用递归函数实现程序思想。

1楼chenfanglincfl昨天 17:26

清晰明了