递归的定义及解题过程

一、递归的定义

要想了解递归，我们首先要了解递归的定义，什么是递归呢？若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。

二、递归的分类

知道了递归的定义，我们再说一下递归的分类，递归分为两种，直接递归和间接递归。直接递归就是自己调用自己。而间接递归可以理解为是A调用了B，而B又调用了A。

三、递归的组成部分

一般地，递归是由递归边界和递归体两部分组成。递归边界确定递归到何时结束,递归体确定递归求解时的递推关系。

四、递归的解题过程

递归的求解的过程均有这样的特征：

先将整个问题划分为若干个子问题,通过分别求解子问题,最后获得整个问题的解。而这些子问题具有与原问题相同的求解方法,于是可以再将它们划分成若干个子问题,分别求解,如此反复进行,直到不能再划分成子问题,或已经可以求解为止。

五、用递归求解斐波那契数列

在700多年前，意大利有一位著名数学家斐波那契在他的《算盘全集》一书中提出了这样一道有趣的兔子繁殖问题。

如果有一对小兔，每一个月都生下一对小兔，而所生下的每一对小兔在出生后的第三个月也都生下一对小兔。那么，由一对兔子开始，满一年时一共可以繁殖成多少对兔子？

用列举法我们可以得到一个如下的数列：

1，1，2，3，5，8，13，21，34，55……

我们可以发现一个规律：后面一个月份的兔子总对数，恰好等于前面两个月份兔子总对数的和。根据这个规律，我们可以写出斐波那契数列中每一项的递归求法：

//斐波那契数列
			
function Fib( n ){
	if(n == 1 || n == 2){  //递归出口
		return 1 ;
	}else{
		return Fib( n - 1 ) + Fib( n - 2 ); //递归体
	}
				
}
			

为了清晰的理解递归过程，我们用一棵树来理解这个函数的执行过程：

递归算法的执行过程是不断地自调用，直到到达递归出口才结束自调用过程；到达递归出口后，递归算法开始按最后调用的过程最先返回的次序返回；返回到最外层的调用语句时递归算法执行过程结束。

该递归结构的Fib(n)算法在计算第n项的斐波那契数列时，必须首先计算第n-1项和第n-2项的斐波那契数列，而某次递归计算得出的斐波那契数列，如Fib(n-1)、Fib(n-2)等无法保存，下一次要用到时还需要重新递归计算，因此其时间复杂度为O(n^2) 。

由此可知，用递归解决问题时，时间效率低，空间开销大，不适合很大规模的问题的求解。