特定序列的递归方法

Question

我正在尝试获取序列在特定位置（序列从 0 开始）的值。此序列的公式为 f(n) = (2^n) - 1，其中 f(0) = 0。

顺序为 f(0) = 0, f(1) = 1, f(2) = 3, f(3) = 7, f(4) = 15，依此类推...

我写这个递归函数是为了找位置。但是，我的数字有点偏差。为什么我的号码不对？

对于这个结果，如果我输入数字 f(4)，我会得到 f(5) -- 31.

中的值

public static int getNumber(int num) {
    if(num == 0) {
        return 1;
    } else {
        return (int)Math.pow(2,num) + getNumber(num-1);
    }
}

我知道问题出在我的基本案例中。我该如何解决？

Answer 1

你说 f(0) = 0，但是你的代码检查是否 num == 0，如果是，returns 1。你只需要 return 0 if num == 0.

尽管我认为您的递归也不会按照您希望的方式正确工作。 2^n - 1可以表示为2的所有次方之和小于小于n，你的是小于等于n的2的次方之和。因此，您可能应该在使用时服用 Math.pow(2, num - 1)。

Answer 2

您的说明说 f(0) 是 0。此外，您的函数不是递归的。我想你想要 2ⁿ - 1 个赞

public static int getNumber(int num) {
    if (num == 0) {
        return 0;
    }
    return (int) (Math.pow(2, num) - 1);
}

我测试了一下，

public static void main(String[] args) {
    for (int i = 0; i < 10; i++) {
        System.out.printf("f(%d) = %d%n", i, getNumber(i));
    }
}

并得到了你预期的结果。当然，您可以使用位移位代替 Math.pow（因为它是 2）。喜欢，

public static int getNumber(int num) {
    if (num == 0) {
        return 0;
    }
    return (1 << num) - 1;
}

得到相同的结果。

特定序列的递归方法

Recursive method for a specific sequence

java

recursion

sequence