栈的应用--递归和进制

一、 栈的应用——递归

在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。

函数怎么可以自己调用自己？听起来有些难以理解，不过你可以不要把一个递归函数中调用自己的函数看做是在调用自己，而就当它是在调用另一个函数。只不过，这个函数和自己长得一样而已。当然，写递归程序最怕的就是陷入永不结束的无穷递归中，所以，每个递归都需要一个退出递归的条件。递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会消耗大量的时间和内存。那么我们讲了那么多递归的内容，和栈有什么关系呢？程序设计基础阶段我们已经了解了递归是如何执行它的前行和退回的。递归过程退回的顺序是它前行顺序的逆序。显然这符合栈的存储方式。简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压如栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。当然，对于现在的高级语言，这样的递归问题是不需要用户来管理这个栈的，一切都由系统代劳就可以了。

##进制

因为栈先进后出的特点，刚好和进制转换数据从后往前读相吻合，所以栈也可以解决进制转换的问题