0

对于我在 uni 的离散结构类，我需要编写一个方法来解决以下公式：  

s[0] = 1

s[n-1] = s[n-2] + n 对于所有 n >= 2

不幸的是，我之前没有实现过很多递归方法，所以我真的不知道自己在做什么。对我来说，事情并没有像往常那样“点击”。

我会以任何可能的方式感谢帮助，但我宁愿完全理解这一点，而不是仅仅复制粘贴别人的工作。

如果 n = 8，则此方法应完成的基本示例...

1 + 2 = 3 ,

3 + 3 = 6 ,

6 + 4 = 10 ,

10 + 5 = 15 ,

15 + 6 = 21 ,

21 + 7 = 28 ,

28 + 8 = 36，我们的答案。

我写了一个方法来解决这个NON递归（如下所示），所以我理解它背后的数学。 

public static int sequenceNonRecursive(int n){
    int[] s = new int[n];
    s[0] = 1;

    if(n >= 2){
        for(int i = 1; i < n; i++){
            s[i] = s[i-1] + i + 1;
        }
    }
    return s[n-1];
}

编辑：我解决了。谢谢大家的帮助！往下看我的答案。

4

6 回答 6

1

重复的定义有点奇怪。我会重写它：

S 0 = 1
S i = S i-1 + i + 1 — ∀ i > 0

该例程可以简化为不使用数组：

public static int sequenceNonRecursive (int n) {
    int S_0 = 1;                      // 0th term is 1
    int S_i = S_0;                    // S_i starts at S_0
    for(int i = 1; i <= n; i++) {
        int S_i_minus_1 = S_i;        // use previous result to calculate next
        S_i = S_i_minus_1 + i + 1;    // next is previous added with index plus 1
    }
    return S_i;
}

任何循环都可以转换为等效的递归例程。诀窍是局部变量变成递归例程的函数参数，循环控制变成if. 如果条件为假，则函数返回结果。否则，函数会像循环体一样进行计算，然后使用递归进行迭代。

作为说明，给定函数：

public static int someFunction (int n) {
    int result = DEFAULT_RESULT;
    for (int i = 0; i < n; ++i) {
        result = UPDATE_RESULT(i, n, result);
    }
    return result;
}

然后，可以将此函数的主体更改为调用递归函数：

public static int someFunction (int n) {
    return someFunctionWithRecursion(n, 0, DEFAULT_RESULT);
}

注意局部变量的初始值是如何被转换为递归例程的参数的。因此，递归例程本身可能如下所示：

public static int someFunctionWithRecursion (int n, int i, int result) {
    if (! (i < n)) {
        return result;
    }
    result = UPDATE_RESULT(i, n, result);
    return someFunctionWithRecursion(n, i+1, result);
}

请注意，在递归调用中，result已更新，并且控制变量i已递增，就像for()在代码的原始循环版本中进行的迭代一样。

顺便说一句：您正在处理的重复实际上有一个封闭的形式：

S n = (½)(n+1)(n+2)

于 2013-09-19T00:28:46.827 回答
0

递归就像将原始问题分解为子问题并尝试解决它们。首先，您需要弄清楚基本情况（在您的情况下是n=0）。现在您可以继续前进，看看如何n > 0通过将案例分解为基本案例来处理案例。n为then n-1then等创建序列n-2直到达到基本情况是递归解决此问题的关键。

于 2013-09-18T23:10:06.387 回答
0

让我们首先将 1 添加到n第二个等式中的所有 ' ：（如果我们增加它们，我们需要减小范围，看到它是正确的应该是微不足道的）

s[0] = 1
s[n] = s[n-1] + (n+1) for all n >= 1

我们为什么要这样做？
简而言之，函数定义是sequence(int n)，不是sequence(int n-1)。

这里s[i]只对应于使用输入参数调用您的函数i。

以及代码的基本思想：

public static int sequence(int n){
    if (/* base case */)
        // return value for base case
    else
        // return other case, includes calling sequence(x) for some x
}

希望这能给你足够的工作。

于 2013-09-18T23:10:09.497 回答
0

它实际上更容易。想象一下，您的方法适用于所有 n，除非 n 为零（基本情况），否则您使用

sequenceRecursive(n-1)

获取前一个数字的值并期望它能够工作。（它会）

在引擎盖下，它将递归到基本情况并在调用返回时建立值。

于 2013-09-18T23:14:05.817 回答
0

我明白了，伙计们。感谢大家的帮助！我无法相信这是多么愚蠢的简单。我一想通，就给了自己一个有力的掌心。我很确定我现在了解递归。

public static int sequenceRecursive(int n){
       if( n == 0 )
            return 0;
        else
            return n + sequenceRecursive(n-1);
}
于 2013-09-20T02:22:53.020 回答
0

像这样构造你的代码（只是给出提示，让你找出问题的其余部分）：

public static int sequenceRecursive(int n){
    if( n == 0 )
        //return something....
    else
        //return something else, which recursively relies on previous values of sequenceRecursive()
}
于 2013-09-18T23:04:53.203 回答