[数据结构与算法]初学者如何快速理解递归？

在c语言中，一个调用自身的函数被称为是递归的(recursive)

递归里面有一个经典题目就是求斐波那契数列

这里我们只要讲如何理解递归，相信看到这篇文章的同学已经初步了解过递归了，这里就不再赘述了

我们直接贴出来用C语言求斐波那契数列的代码如下

int fib(int i)
{
	if(i <= 1)
	{
		return i;
	}
	else
	{
		return fib(i - 1) + fib(i - 2);
	}
}

对于部分初学的同学，面对要求用递归求解的题目，可能会摸不着头脑，到底怎么写出递归的代码？我的方法是可以把递归和高中时所学的方程联系起来

我对于初级的递归题目的解题思路总结了两个步骤，递归递归，分为“递”和“归”两步，所以我们

第一步要搞清楚它是怎么传递的，拿斐波那契数列数列举例，通过寻找规律，我们可以很容易的找出斐波那契数列数列符合方程，就是我们中学时学过的方程的样式，目前我见到的递归题目都是可以写出这样的方程的

第二步，我们要找出来它在哪里“归”，也就是它的出口在哪里。我们从高中数学的角度来看f(x)=f(x-1)+f(x-2),(x>=2)这个式子，我们如何求出来某个f(n)的值？比如n=100，我们如何求出f(100)的值，答案是我们无法求出某个f(n)的值，因为我们不知道出口在哪？试想一下，在我们求值的时候，上面这个式子是不是还可以分裂为两个式子，f(x-1)=f(x-2)+f(x-3)和f(x-2)=f(x-3)+f(x-4)

?如果我们不告诉编译器f(n)到f(0)之间的某个值，那么他就会一直传递下去，一直到取值范围的边界，但如果我们告诉编译器当x小于或等于某个值时就返回一个确定的值，那么当程序程序传递到这个值时就会立刻返回，这就是我们所说的出口，所以说出口是构成递归的两个重要元素之一。

明白了递归的两个重要元素，问题就迎刃而解了，一是写出方程，二是找出出口

当然这个出口我们不是只能设置在x<=1处，还可以设置在其它地方，只不过设置在其他地方可能就不符合斐波那契数列的方程了，但是它仍是一个递归函数