LeetCode 递归（Recursion） 培训专题 讲解文章翻译 （附链接）
递归 -时间复杂度
在本文中,我们主要介绍如何分析递归算法程序中的时间复杂度。.
正如之前的问题printReverse所描述的， 需要把一个字串逆序输出.其中一种递归的解法如下所示: printReverse(str) = printReverse(str[1...n]) + print(str[0]) 其中str[1...n]是输入的字串str去除了首字母str[0]的切分子串， . 显而易见，这个算法会连续调用n次,这个n也就该输入字串的长度.在每次递归的最后,我们只打印首字母,因此该算法每次调用递归所耗费的时间为常量,即为{\mathcal{O}(1)}O(1). 把次数和每次耗时进行合计，该递归程序printReverse(str)的耗时即为 (printReverse) = n * O(1) = O(printReverse)=n∗O(1)=O(n).
对于递归函数,像上面的线性化递归调用的栗子其实是很少的，更多的是非线性的.例如,之前章节我们讨论的Fibonacci number，它的递归关系就定义为更复杂的f(n) = f(n-1) + f(n-2).乍看之下,很难一下子去计算出斐波那契函数的递归调用次数 -_-.
在前面的章节中,我们讨论过用来优化递归算法时间复杂度的记忆化方法.通过存储和重复使用中间变量,记忆化能够极大地降低递归程序的调用次数,换个说法就是减少执行树中的递归调用分支.在分析试用了记忆化的递归调用程序的时间复杂度时，千万要记得考虑这种（分支减少的）情况。. 让我们重新再回看前面斐波那契额数列的栗子.使用记忆化方法的话，我们每次都将斐波那契额数列在n.节点下的存储，于是我们可以确保对于每个节点计算需要的递归调用只需要一次.而且我们知道斐波那契额数列的递归关系是每个f(n)都依赖前一个n-1的结果.最终使得计算f(n)只调用n-1次之前已经计算好的结果即可. 现在,我们可以很轻易的通过前面介绍的公式 O(1)∗n=O(n).来计算斐波那契额数列函数的时间复杂度。记忆化不仅仅优化算法的时间复杂度，同样也简化了对于时间复杂度的计算。 在下一篇文章中,我们将讨论如何估算递归程序的空间复杂度. 原文地址：https://leetcode.com/explore/learn/card/recursion-i/256/complexity-analysis/1669/ 优质内容筛选与推荐>>
1、数组相关
2、Exchange 邮件服务器内存硬盘估算
3、史玉柱湖畔大学演讲：想做脑白金神级产品，要过这3个关
4、Midori 0.5 发布，轻量级跨平台网页浏览器
5、Math Common Sense 数学小常识
在本文中,我们主要介绍如何分析递归算法程序中的时间复杂度。.
在一个递归程序中,它的时间复杂度 O(T)一般来说就是他总共递归调用的次数(定义为 R)以及每次调用时所花费的耗时(定义为 O(s)) ，这样我们就可以得出: (T) = R * O(T) = R∗O(s)下面让我们来看几个栗子：
线性的栗子
正如之前的问题printReverse所描述的， 需要把一个字串逆序输出.其中一种递归的解法如下所示: printReverse(str) = printReverse(str[1...n]) + print(str[0]) 其中str[1...n]是输入的字串str去除了首字母str[0]的切分子串， . 显而易见，这个算法会连续调用n次,这个n也就该输入字串的长度.在每次递归的最后,我们只打印首字母,因此该算法每次调用递归所耗费的时间为常量,即为{\mathcal{O}(1)}O(1). 把次数和每次耗时进行合计，该递归程序printReverse(str)的耗时即为 (printReverse) = n * O(1) = O(printReverse)=n∗O(1)=O(n).
执行树
对于递归函数,像上面的线性化递归调用的栗子其实是很少的，更多的是非线性的.例如,之前章节我们讨论的Fibonacci number，它的递归关系就定义为更复杂的f(n) = f(n-1) + f(n-2).乍看之下,很难一下子去计算出斐波那契函数的递归调用次数 -_-.
在这个例子里,我们最好使用execution tree这个工具可以用来直观地表示递归程序的执行流.树中的每一个节点都表示每次对应的递归程序调用.因此,树中的节点总数与整个递归过程调用的总数相对应。递归函数的执行树会形成一个n-ary tree,其中n就是这个程序执行下来递归调用的次数.例如,斐波那契函数的执行流就是一个二叉树,如下图所示就是计算f(4)的流程树： 在一个n层的满二叉树,所有节点数总和应该是 2^n - 1 .因此,对于递归程序f(n)总调用次数的上限也应该是 {2^n -1} .所以,我们得出了递归程序f(n)的时间复杂度即为 {\mathcal{O}(2^n)}
记忆化
在前面的章节中,我们讨论过用来优化递归算法时间复杂度的记忆化方法.通过存储和重复使用中间变量,记忆化能够极大地降低递归程序的调用次数,换个说法就是减少执行树中的递归调用分支.在分析试用了记忆化的递归调用程序的时间复杂度时，千万要记得考虑这种（分支减少的）情况。. 让我们重新再回看前面斐波那契额数列的栗子.使用记忆化方法的话，我们每次都将斐波那契额数列在n.节点下的存储，于是我们可以确保对于每个节点计算需要的递归调用只需要一次.而且我们知道斐波那契额数列的递归关系是每个f(n)都依赖前一个n-1的结果.最终使得计算f(n)只调用n-1次之前已经计算好的结果即可. 现在,我们可以很轻易的通过前面介绍的公式 O(1)∗n=O(n).来计算斐波那契额数列函数的时间复杂度。记忆化不仅仅优化算法的时间复杂度，同样也简化了对于时间复杂度的计算。 在下一篇文章中,我们将讨论如何估算递归程序的空间复杂度. 原文地址：https://leetcode.com/explore/learn/card/recursion-i/256/complexity-analysis/1669/ 优质内容筛选与推荐>>
1、数组相关
2、Exchange 邮件服务器内存硬盘估算
3、史玉柱湖畔大学演讲：想做脑白金神级产品，要过这3个关
4、Midori 0.5 发布，轻量级跨平台网页浏览器
5、Math Common Sense 数学小常识