为方法编写递归关系

发布于 2024-09-24 17:34:26 字数 261 浏览 4 评论 0原文

我有一些代码，需要为其编写一个递归关系。该代码仅计算 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)
}

原文

I have a bit of code and need to write a recurrence relation for it. The code simply calculates 2 raised to the nth power.
Any help is appreciated.

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)
}

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

陌若浮生 2024-10-01 17:34:26

函数的表述几乎是递推关系。基本上，您需要做的就是执行变量更改，以便递归中 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);
    }
}

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

fib₀=1
fib₁=1
fib_n+2 = fib_n+1 + fib_n

使用斐波那契示例，您实际上不需要执行变量的更改。但是，使用 two 函数，可以更轻松地编写关系。

The formulation of the function almost is a recurrence relation. Basically, all you need to do is perform a change of variables so the argument to two in the recursion is n. For example, take the following Fibonacci function:

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

You wouldn't want to use that implementation, since it's horribly inefficient, but it makes writing the recurrence relation easy:

fib₀=1
fib₁=1
fib_n+2 = fib_n+1 + fib_n

With the fibonacci example, you don't actually need to perform the change of variables. However, with your two function, it will make it simpler to write the relation.

回复收藏 0 原文

天煞孤星 2024-10-01 17:34:26

没有递归调用的行是在恒定时间内完成的，我们将其称为 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)。

The lines that don't have recursive calls are done in a constant time that we will call c.

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

After each recursive call with n odd, the next recursive call we be with n-1 even.
So in the worst case we start with n odd -> n-1 is even -> (n-1)/2 is odd -> (n-1)/2-1 is even and so on...

If for example we start with n=19 then 19 is odd -> 18 is even -> 9 is odd -> 8 is even -> 4 is even -> 2 is even -> 0.

The depth of the recursive tree is about lgn, and since on each level there are c operations then the running time is clgn=O(lgn).

回复收藏 0 原文

~没有更多了~