java - 为方法编写递归关系

Question

我有一些代码，需要为它写一个递归关系。该代码只是计算 2 的 n 次方。任何帮助表示赞赏。

public static int two(int n) {

     if (n==0) {
       return 1;
     } else if (n%2 == 0) {
       int x = two(n/2);
       return x*x;
     } else { 
       return 2 * two(n-1)
}

Answer 1

函数的表述几乎是一个递推关系。基本上，您需要做的就是更改变量，因此two递归中的参数是n. 例如，采用以下斐波那契函数：

public static int fib(n) {
    if (n==0) {
        return 1;
    } else if (n==1) {
        return 1;
    } else {
        return fib(n-1) + fib(n-2);
    }
}

您不想使用该实现，因为它的效率非常低，但它使编写递归关系变得容易：

纤维0 =1
纤维1 =1
fib n+2 = fib n+1 + fib n

对于斐波那契示例，您实际上不需要执行变量的更改。但是，使用您的two函数，它将使编写关系变得更简单。

Answer 2

没有递归调用的行在我们称为 c 的恒定时间内完成。

T(n)=T(n-1)+c if n is odd.
T(n)=T(n/2)+c if n is even.

在每次递归调用 n 奇数之后，下一次递归调用我们将使用 n-1 偶数。所以在最坏的情况下，我们从 n 奇数开始 -> n-1 是偶数 -> (n-1)/2 是奇数 -> (n-1)/2-1 是偶数等等......

例如，如果我们从 n=19 开始，那么 19 是奇数 -> 18 是偶数 -> 9 是奇数 -> 8 是偶数 -> 4 是偶数 -> 2 是偶数 -> 0。

递归树的深度约为 lgn，由于每一层都有 c 个操作，因此运行时间为 clgn=O(lgn)。