在此之前，我们介绍了动态规划、深度优先搜索等基础算法，但是，有部分好友评论说，难度太难了，我们知道动态规划的自顶向下跟深度优先搜索一般都用递归实现，今天我们就先来讲讲算法与数据结构中，基础中的基础递归。讲递归之前，我们先来了解下栈。
栈是一种基础的数据结构，每次操作的都是栈顶的数据。我们称栈顶的方向为上，栈底的方向为下，只有上面的元素已经出栈了，下面元素才能出栈，我们称之为先进后出。好比这个图中健身器材，这实际上就是一个栈，最小最上面的那块铁最后安装进去，却最先被取出来，最大的那个铁圈，最早安装进去，最晚取出来。(找了好久才找到一个现实生活中常见又大众的例子，作为一个程序员，生活真的是比较单调)
栈是一种支持Push跟Pop两种数据结构，他的基本操作如下图所示，每次push操作，实际上都是往栈的上方插入一个元素，Pop操作，则是把栈最上方的元素弹出来。
那么这个栈跟我们要讲的递归到底是什么关系呢？我们先看一看这个问题，求一个数的阶乘，一个正整数的阶乘是1到它本身所有正整数的乘积，我们用递归的方式来实现这个功能。
这个代码在操作系统里面是怎么执行的呢，操作系统本身就有一个运行时候的栈。我们假设求5的阶乘，操作系统执行到第5行，发现这是一个递归，就会把它加到系统栈里面，并且记录下我在执行fact方法，x等于5，执行到第5行，然后开始计算4，执行到第5行，发现是个递归，又把他记录到系统栈里面，记录下，正在执行fact方法，x等于4，计算到第5行。。。直到执行到x等于1，然后退出，系统开始退栈，回到刚才X等于2的时候，从第5行开始执行，然后执行第6行，接着退出，执行x=3的时候。。。最后，到了栈底x=5，计算完之后栈没有元素了，整个方法执行完毕！
我们常常说暴栈，也就是Stack Overflow，说的就是系统栈溢出，造成这种问题的一般原因都是因为递归没有退出条件！所以操作系统不停递归，类似与死循环。上述例子中，当x等于的时候就退出，就是退出条件。另外一种可能，是本身数据量就非常大，也有可能会造成Stack Overflow，这种一般的解决方法也有三种，一是增大系统栈空间，二是使用非递归的方法，三是减少递归过程中栈空间的使用。
好了，今天的算法我们就讲到这里，相信你再阅读下面的动态规划算法跟深度优先搜索算法，会有进一步的理解。有什么疑问可以随时提出。
网友评论