2

基本上，我正在寻找一个程序，它会给我序列但最多一定数量。所以假设我想上升到第 20 个数字或其他数字。我想知道如何递归地迭代它，以便它只需使用if()语句就可以找到序列中每个数字的值，直到该数字。我没有任何代码，因为我只知道如何使用for循环来完成，这不是我需要的方法。

我至少知道这一点：

if n = 1 || n = 0
   return n;
else 
    return F(n-1) + F(n-2);

代码：

class Fibonocci {

    public static int factorial(int i,int n) { 
        System.out.println(i);

        if(i==n || n==0 || n==1) {  // base case;  when i = n, we're done.
            return n; 
        } else {
            return i + 1 + factorial(i+2,n); // iterative case; we're still adding values up.
        }
    }

    public static void main(String[] args)
    {
        Fibonocci test= new Fibonocci();
        System.out.println( test.factorial(0,10) );
    }
}

我一直在尝试那个和一大堆其他尝试，但我仍然很难过。我知道它去0 1 1 2 3 5 8 13 21 34...

4

2 回答 2

5

你会感到惊讶，但你的代码几乎就在那里。我的感觉是你对递归还不满意。

你可以迭代地做的任何事情都可以递归地做。

可以这样想：一个循环（for、while、do-while）有一个迭代步骤，以及一个检查它是否完成的条件。例如，如果我将 1 到 n 的所有数字相加：

int sum = 0;
for(int i = 1; i <= n; i++) { // Condition to check completion
    sum += i;  // iterative step
}

要将其转换为递归函数，我需要一个完成条件（称为基本案例）和一个迭代步骤或迭代案例。总而言之，我的基本情况是 when i==n。

public int sum(int i, int n) {
    if(i == n) {  // base case;  when i = n, we're done.
        return n; 
    } else {
        return i + sum(i+1, n); // iterative case; we're still adding values up.
    }
}

将此应用于您的斐波那契方法，我认为您会没事的。不，真的，用适当的参数将它包装在一个函数调用中，你会没事的。

进一步澄清：电话是如何扩大的？

回到求和方法，假设我想对 1 到 10 之间的数字求和。调用是如何扩展的？

迭代地

真的，调用堆栈上没什么用。它正在经历一个循环。但是，我们可以综合每次通过时发生的事情。

int sum = 0;
for(int i = 1; i <= 10; i++) {
    sum += i;
}

通过循环看起来像这样：

Cycle #1: sum=1
Cycle #2: sum=3
Cycle #3: sum=6
Cycle #4: sum=10
Cycle #5: sum=15
Cycle #6: sum=21
Cycle #7: sum=28
Cycle #8: sum=36
Cycle #9: sum=45
Cycle #10: sum=55
Sum = 55

到目前为止似乎是对的。

我们只是每次取一个元素并将其添加到一个集体总和值中。本质上，1+2+3+4+5+6+7+8+9+10 被分解为以下方式：

sum += 1 // 1 now
sum += 2 // 3 now
sum += 3 // 6 now
...
sum += 10 // 55 now

递归地，值的收集方式没有任何区别，但它的完成方式略有不同。

递归

检查对此的调用：

public int sum(int i, int n) {
    return n == i ? n : i + sum(i+1, n); // ternary if-else statement, the exact same as the if-else in the above sum method.
}

1 + sum(2, 10)
1 + 2 + sum(3, 10)
1 + 2 + 3 + sum(4, 10)
1 + 2 + 3 + 4 + sum(5, 10)
1 + 2 + 3 + 4 + 5 + sum(6, 10)
1 + 2 + 3 + 4 + 5 + 6 + sum(7, 10)
1 + 2 + 3 + 4 + 5 + 6 + 7 + sum(8, 10)
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + sum(9, 10)
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + sum(10, 10)
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
55

本质上，它在递归调用中的作用与在串行调用中的作用相同。扩展有点有趣，但是一旦你习惯了它，它就不会是一个挑战。

从这里开始，我强烈建议您尝试一下。不要害怕尝试；此处提供的信息足以让您入门。

于 2012-04-18T01:01:23.837 回答
2

让我通过编写递归阶乘函数来帮助您：

阶乘方法定义为：

 if n == 0 || n == 1 return 1; else return n * F(n - 1);

可以用Java编写为：

public int factorial(int n) { 
   if(n == 0 || n == 1) { 
       return 1;
   } else { 
       return n * factorial(n - 1);
   }
}

因此，鉴于您所知道的，我认为这足以让您适应和测试斐波那契数列。

于 2012-04-18T00:56:40.940 回答