C++递归算法详解.docx

 本文试图从以下几个方面来讲解递归  1、什么是递归？  2、递归算法通用解决思路  3、实战演练（从初级到高阶）  4、递归函数调用栈  5、递归算法时间复杂度分析与求解  力争让大家对递归的认知能上一个新台阶，特别会对递归的精华:时间复杂度作详细剖析，会给大家总结一套很通用的求解递归时间复杂度的套路，相信你看完肯定会有收获。  简单地说，就是如果在函数中存在着调用函数本身的情况，这种现象就叫递归。  以阶乘函数为例,如下, 在 f 函数中存在着 f(n - 1) 的调用，所以此函数是递归函数。  进一步剖析「递归」，先有「递」再有「归」，「递」的意思是将问题拆解成子问题来解决， 子问题再拆解成子子问题，...，直到被拆解的子问题无需再拆分成更细的子问题（即可以求解），「归」是说最小的子问题解决了，那么它的上一层子问题也就解决了，上一层的子问题解决了，上上层子问题自然也就解决了,....,直到最开始的问题解决,文字说可能有点抽象，那我们就以阶层 f(6) 为例来看下它的「递」和「归」。  求解问题 f(6), 由于 f(6) = n * f(5), 所以 f(6) 需要拆解成 f(5