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