一、递归的优缺点

递归是什么

程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。

一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

递归的优缺点

优点：代码更简洁清晰，可读性更好

递归的话函数调用是有开销的，而且递归的次数受堆栈大小的限制。

缺点：

时间和空间消耗比较大。每一次函数调用都需要在内存栈中分配空间以保存参数，返回地址以及临时变量，而且往栈里面压入数据和弹出都需要时间。

另外递归会有重复的计算。递归本质是把一个问题分解为多个问题，如果这多个问题存在重复计算，有时候会随着n成指数增长。斐波那契的递归就是一个例子。

递归还有栈溢出的问题，每个进程的栈容量是有限的。由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能系统撑不住。

延伸阅读：

二、递归的程序特性

优雅性

相比其他解法（比如迭代法），使用递归法，你会发现只需少量程序就可描述出解题过程，大大减少了程序的代码量，而且很好理解。递归的能力在于用有限的语句来定义对象的无限集合。

反向性

由于递归调用程序需要维护调用栈，而栈（我们在上文提过）具有后进先出的特征，因此递归程序适合满足取反类需求。我们在第五部分有一些编程实践，比如字符串取反，链表取反等相关有趣的算法问题。

递推关系

递归程序可以较明显的发现递推关系，反过来也可以这么说，具有递推关系的问题基本都可以通过递归求解（当然也许有性能更佳的解法，但递归绝对是一种选择）。递推关系常见问题有杨辉三角、阶乘计算。

上一篇

在函数式编程中，什么是累加器?

下一篇

做进度计划用什么软件?