递归调用代价

在链表这一章，所有的递归算法都作用在线性结构上。通常对于线性结构，是非常容易将递归转为非递归的。通常对于生产代码来说，在线性结构上，不应该使用递归算法。（但在面试中，你也可能遇到面试官一定你将某个基于链表的算法实现成递归算法的情况，主要是在考查你对递归的理解，而不是说这种算法一定要写成递归算法。）

对于非线性的结构（比如这个课程后续的重点，树形结构），使用递归是常见的。（另外，对于很多递归算法，比如归并排序或者快速排序，本质也是在一个“隐性”的递归树上做事情。）

此时，问题的关键是，算法作用的树是否平衡。这就是平衡树这个概念为什么异常重要的原因。一个有 10 亿规模数据的数据结构，如果平衡，其高度不过 30。(log2(10 亿) = 30)。而一棵有 100 层的二叉树，只要平衡，其能容纳的数据规模，是大于宇宙中的原子数量的。而 100 这个递归深度，对于现代计算机来说，是不可能导致栈溢出的。

也正是因为如此，这个课程后续的很多算法或者数据结构优化的过程，都是贺词相关的。比如快速排序算法中使用随机标定点的方式，避免让递归树退化；比如 AVL 树或者红黑树避免了二分搜索树的退化；而很多结构在设计之初，就考虑了这一点，根本就没有退化的可能性（完全二叉树），比如堆或者线段树。在这个课程后续学习这些内容的时候，你可以进一步体会这些设计背后的原因。

另一个思路则是进一步加大树的分支数量，让一棵树更“平”。log2（10 亿） = 30；log10（10 亿）= 9。在这个课程的最后一章，你将看到一些算法和数据结构的设计思路着眼于这种方式。

通常在现代计算机上，只要考虑了“递归树”的平衡性，基本上就不会出现栈溢出。但不排除在一些特别“敏感”的编程环境中，还是希望尽量避免递归的调用，比如在嵌入式开发中（但随着芯片越来越强大，这一点在嵌入式开发中也在慢慢变得不重要。）此时，就需要考虑把递归算法改写成非递归算法。所有的递归算法一定能改写成非递归算法。方法是自己手动设置一个栈，去模拟系统栈的运行。但这个方式对于初学者来说不是一定要掌握的。

继续加油！：）