我正在学习Java递归，但是被卡在以下问题上。
void f(int n) {
if (n<=1) return;
f(n/2);
System.out.writeln("still continuing...");
f(n/2);
f(n/2);
}
我对此有两个问题。
如果我们说T（n）是程序打印的行数，n是输入，那么T（n）的递归公式是什么？
我如何不使用主定理来解决问题1的重复？
干杯
最佳答案
让我们从T（n）的值的公式开始。我们知道以下内容：
以0或1作为参数调用f需要时间O（1）
用较大的值调用f会使f（n / 2）进行三个调用，并执行其他恒定的工作量。
因此，我们可以得到以下重复：
T（1）≤1
T（n）≤3T（n / 2）+1
请注意，我在这里使用的是“ +1”而不是“ + O（1）”。从数学上讲这还很不确定，但是由于我们一直在寻找以big-O表示法表示的最终结果，因此这并不是一个太大的问题。
现在，我们将如何解决这个问题？一种选择是为n插入一些任意值，然后看看会发生什么。我们从（假设n> 1）开始
T（n）≤3T（n / 2）+1
现在，让我们考虑一下对T（n / 2）的调用。如果n / 2> 1，那么我们得到
T（n）≤3T（n / 2）+1
≤3（3T（n / 4）+1）+1
= 9T（n / 4）+ 3 +1
现在，让我们扩大收益：
T（n）≤9T（n / 4）+ 3 +1
≤9（3T（n / 8）+ 3）+ 3 +1
= 27T（n / 8）+ 9 + 3 +1
在这一点上，我们可以看到一种模式正在出现。在递归迭代之后，我们得到的总工作量是
T（n）= 3iT（n / 2i）+ sum（i = 0至i-1）3i
当n / 2i≤1时，该过程终止；当i≈lg n时，该过程终止。如果我们插入lg n，我们得到
T（n）≤3lg nT（1）+ sum（i = 0至i-1）3i）
≤3lg n +总和（i = 0至i-1）3lg n
现在，3lg n = 3（log3 n / log3 2）= 3log3 n1 / log3 2 = n1 / log3 2，所以整个事情是
T（n）≤n1 / log3 2 + sum（i = 0至（lg n）-1）3i
使用几何级数和的公式，该最后一项为（3lg n-1）/ 2，最终扩展为O（n1 / log3 2），因此，总的来说，该表达式为O（n1 / log3 2）。
但是这个公式真的很丑。我们可以简化一下吗？好吧，我们有这个：
1 / log3 2 = log2 3
这使我们的运行时间为O（nlg 3），大约为O（n1.58）。
希望这可以帮助！