一文搞定递归、非递归的左右互搏术 _生活知道

引言
本系列的第6篇《再不会“降维打击”你就Out了!》讲述了递归算法的意义、套路，第7篇《神力加身！动态编程》讲述了递归算法的优化，但是在大量的实际项目、工程和大家关心的求职面试中，却会碰到大量消除递归的需求。于是产生了两个问题：
1. 为什么会有消除递归的需求？
2. 如果都采用非递归的方式，那么递归算法的独特价值又是什么呢？
本文以此为引子，将以你在任何其他算法书中都不会看到的方式，向你揭示递归的高阶技巧，让你彻底掌握递归与非递归的左右互搏之术。
今天的小汽车会逐步加速，各位乘客要系好安全带：）
1. 从哪里来、回到哪里去
递归算法在运行的时候，是不断重入同一函数的，既然是重入，就必然要搞清楚一个基本的问题——从哪里来、回到哪里去？
用专业一点的术语讲，就是要解决“上下文”问题。
当今流行的经典计算机体系结构和编程语言都采用堆栈来解决上下文的保存和恢复问题。
2. 什么是堆栈？
堆栈本质用以下两点概括：

一段存储空间（通常是内存）；

一组向这段存储空间存、取数据的操作。它满足“后进先出”原则。

打个形象的比方：
堆栈就相当于茶壶，向堆栈中存数据就相当于向茶壶里加水，取数据就相当于从茶壶里倒出水。
很显然，最新加进茶壶的水在最上层，从茶壶里倒出水的时候，也是这部分水先被倒出来。
3. 堆栈的好处是什么？
用一句通俗的话来总结就是：历史倒序回放，只问元芳：）
把每次放入数据的动作，看作是历史上的一个时刻的话，那么N次放入数据，就相当于历史上的N个时刻。它们组成了一段历史，这段历史保存在了堆栈中。
从堆栈中取数据，就相当于回放一个历史时刻。根据堆栈操作的“后进先出”原则，堆栈中每次取出的“历史时刻”都是“最近时刻” 。将堆栈中的数据逐一取出，就相当于将历史倒序回放。
从上面的过程可以看出，每次倒放“最近时刻”的时候，不需要管当前状态，只要简单向堆栈这个“元芳”要就
【一文搞定递归、非递归的左右互搏术】以上就是朝夕生活（www.30zx.com）关于“一文搞定递归、非递归的左右互搏术”的详细内容，希望对大家有所帮助！

一文搞定递归、非递归的左右互搏术

猜你喜欢