我难以决定的简单递归方法大O。 我不能换我的头周围，当一个方法被调用多次发生了什么。 我想具体谈谈我的困惑的地方，但此刻我试图回答一些硬件问题，代替不想骗的，我问那人回答这个职位拿出一个简单的递归方法提供该方法的大O的一个简单的解释。 （最好在Java中...语言我正在学习。）
谢谢。
Answer 1:
您可以定义的顺序递归为好。 举例来说，假设你有一个函数f。 为了计算F（N）取k步。 现在你要计算F（N + 1）。 比方说F（N + 1）调用f（n）的一次，然后F（N + 1）取K +一些常数的步骤。 每次调用会采取一些步骤恒定额外，因此这种方法是O（n）。
现在看看另一个例子。 比方说，你加入了前两次的结果天真地实现斐波那契数：
fib(n) = { return fib(n-1) + fib(n-2) }
现在让我们说你可以（N-1）无论是在约k步计算FIB（N-2）和FIB。 为了计算FIB（N），则需要K + K = 2 * k个步骤。 现在让我们说你要计算FIB（N + 1）。 因此，你需要两倍的步骤为FIB（N-1）。 因此，这似乎是O（2 ^ N）
诚然，这是不是很正规，但希望这样你可以得到一个有点感觉。
Answer 2:
您可能要参考主定理寻找的递归方法大O。 这是维基百科的文章： http://en.wikipedia.org/wiki/Master_theorem
你要觉得像树的递归问题。 然后，考虑树的每个级别和工作所需的量。 问题一般分为3类，根重（树的第一次迭代>>休息），平衡（每个级别都有工作的等量），叶重（树的最后一次迭代>>休息）。
以合并排序为例：
define mergeSort(list toSort):
if(length of toSort <= 1):
return toSort
list left = toSort from [0, length of toSort/2)
list right = toSort from [length of toSort/2, length of toSort)
merge(mergeSort(left), mergeSort(right))
你可以看到，依次归并的每一个呼叫电话2个mergeSorts的1/2的原始长度。 我们知道，被合并值的数量合并过程需要一定的时间比例。
复发关系则T（N）= 2 * T（N / 2）+ O（n）中。 两个来自2级的呼叫和n / 2是从每一个呼叫仅具有一半的元素数。 然而，在每一级有相同数量的元素的n个需要被合并，因此在每一个水平的恒定工作为O（n）。
我们知道工作是均匀分布的（O（n）中每一深度）和树是log_2（N）深，做递归函数的大O是O（n *的log（n））。
文章来源: Big O of Recursive Methods
