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

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

fib0=1
fib1=1
fibn+2 = fibn+1 + fibn

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