下载掌阅APP，畅读海量书库
立即打开
在计算机程序设计中，若一个函数在其函数体内又直接或间接调用了自身，则称之为递归函数。递归的例子在生活中比比皆是，如“从前有座山，山里有个庙，庙里有个老和尚，老和尚给小和尚讲故事……”，新闻联播中主播身后背景中的电视画面又出现了主播，等等。
要理解递归，仅了解递归的概念远远不够，需要从本质上掌握递归的特性、递归的使用场景以及递归存在的局限，才能够看得懂、写得出递归程序。因为递归是在函数内部调用其自身，所以递归要解决的必定是可重复性问题。计算机程序的实现是有穷的，需要在一定时间内执行完毕，故而递归程序不可能一直执行，必定在某个时刻到达出口，这就决定了问题的规模是逐渐递减的。从上述分析可以得出递归的本质特性如下。
（1）问题及其子问题有相同的结构。
（2）子问题的规模逐渐递减。
（3）有终止条件作为出口。
用递归算法解决问题时，程序简洁清晰，易于理解，但递归程序调试复杂，真正理解相当不易。需要注意的问题是，由于函数调用的开销和子问题的重复求解，递归程序效率不高。因此，处理复杂问题时，递归程序往往需要与动态规划等算法相结合使用。