先来先服务算法代码_程序员算法与数据结构基础中的基础，栈与递归

在此之前&＃xff0c;我们介绍了动态规划、深度优先搜索等基础算法&＃xff0c;但是&＃xff0c;有部分好友评论说&＃xff0c;难度太难了&＃xff0c;我们知道动态规划的自顶向下跟深度优先搜索一般都用递归实现&＃xff0c;今天我们就先来讲讲算法与数据结构中&＃xff0c;基础中的基础递归。讲递归之前&＃xff0c;我们先来了解下栈。

栈是一种基础的数据结构&＃xff0c;每次操作的都是栈顶的数据。我们称栈顶的方向为上&＃xff0c;栈底的方向为下&＃xff0c;只有上面的元素已经出栈了&＃xff0c;下面元素才能出栈&＃xff0c;我们称之为先进后出。好比这个图中健身器材&＃xff0c;这实际上就是一个栈&＃xff0c;最小最上面的那块铁最后安装进去&＃xff0c;却最先被取出来&＃xff0c;最大的那个铁圈&＃xff0c;最早安装进去&＃xff0c;最晚取出来。(找了好久才找到一个现实生活中常见又大众的例子&＃xff0c;作为一个程序员&＃xff0c;生活真的是比较单调)

栈是一种支持Push跟Pop两种数据结构&＃xff0c;他的基本操作如下图所示&＃xff0c;每次push操作&＃xff0c;实际上都是往栈的上方插入一个元素&＃xff0c;Pop操作&＃xff0c;则是把栈最上方的元素弹出来。

那么这个栈跟我们要讲的递归到底是什么关系呢&＃xff1f;我们先看一看这个问题&＃xff0c;求一个数的阶乘&＃xff0c;一个正整数的阶乘是1到它本身所有正整数的乘积&＃xff0c;我们用递归的方式来实现这个功能。

这个代码在操作系统里面是怎么执行的呢&＃xff0c;操作系统本身就有一个运行时候的栈。我们假设求5的阶乘&＃xff0c;操作系统执行到第5行&＃xff0c;发现这是一个递归&＃xff0c;就会把它加到系统栈里面&＃xff0c;并且记录下我在执行fact方法&＃xff0c;x等于5&＃xff0c;执行到第5行&＃xff0c;然后开始计算4&＃xff0c;执行到第5行&＃xff0c;发现是个递归&＃xff0c;又把他记录到系统栈里面&＃xff0c;记录下&＃xff0c;正在执行fact方法&＃xff0c;x等于4&＃xff0c;计算到第5行。。。直到执行到x等于1&＃xff0c;然后退出&＃xff0c;系统开始退栈&＃xff0c;回到刚才X等于2的时候&＃xff0c;从第5行开始执行&＃xff0c;然后执行第6行&＃xff0c;接着退出&＃xff0c;执行x&＃61;3的时候。。。最后&＃xff0c;到了栈底x&＃61;5&＃xff0c;计算完之后栈没有元素了&＃xff0c;整个方法执行完毕&＃xff01;

我们常常说暴栈&＃xff0c;也就是Stack Overflow&＃xff0c;说的就是系统栈溢出&＃xff0c;造成这种问题的一般原因都是因为递归没有退出条件&＃xff01;所以操作系统不停递归&＃xff0c;类似与死循环。上述例子中&＃xff0c;当x等于的时候就退出&＃xff0c;就是退出条件。另外一种可能&＃xff0c;是本身数据量就非常大&＃xff0c;也有可能会造成Stack Overflow&＃xff0c;这种一般的解决方法也有三种&＃xff0c;一是增大系统栈空间&＃xff0c;二是使用非递归的方法&＃xff0c;三是减少递归过程中栈空间的使用。

好了&＃xff0c;今天的算法我们就讲到这里&＃xff0c;有什么疑问可以随时提出。有帮助到的朋友点赞加关注哦&＃xff0c;我会持续更新。