如何计算递归函数的值

Question

i具有递归函数：t（n）= 2t（n/2） n。我想通过将不同的参数传递给函数并获取函数值来找到函数的复杂性。然后，我将猜测功能的公式（例如n，n*log（n））。

我编写以下代码：

public static void main(String[] args) {
    System.out.println(findValueOfTheFunction(2));
    System.out.println(findValueOfTheFunction(4));
    System.out.println(findValueOfTheFunction(8));
}
static double findValueOfTheFunction(double n) {
    if(n > eps) {
        return 2*findValueOfTheFunction(n/2) + n;
    }
    else return 0;
}}

我从代码中得到三分。P1（2，10）和P2（4，24）和P3（8，56）。

理解，递归函数的复杂性为o（n）= n*log（n）。但是我的观点不适合公式。

我在这里做了一些研究，但是似乎没有人有类似的问题。

Answer 1

您的第一个问题在这里：

 else return 0;

在某个时候；你的递归结束了；并达到这一点。

然后您开始乘以最后一个通话的结果...猜猜x * y * z * ... * 0可能会计算到？！

因此，您的所有方法都在返回一些m * n值（其中n是您的输入； m取决于您递归调用自己的方法的频率。当您的代码转换为：

时

  if (n>eps) {
    return n + findValueOfTheFunction(n/2)

长话短说：您的计算将失去其结果的"有趣"部分。所以 - 而不是返回0 ...返回1！

Answer 2

您是否必须为此编写代码？您可以通过给予n并替换值来进行一些数学：

t(1) = 2t(1/2) + 1
t(2) = 2t(1) + 1 = 2(2t(1/2)+1) = 2*2t(1/2)
t(4) = 2t(2) + 1 = 2*2*2*t(1/2)
t(8) = 2t(4) + 1 = 2*2*2*2*t(1/2)

剩余的2*1并不重要，您可以继续使用t（1/2）部分。我想已经有些事情了。