java - 将迭代方法转换为递归方法 (Java)

Question

对于我在大学的离散结构类(class)，我需要编写一个方法来求解以下公式:

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，我们的答案。

我已经编写了一种方法来递归地解决这个非问题(如下所示)，所以我确实理解其背后的数学原理。

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

编辑:我解决了。谢谢大家的帮助!请看下面我的回答。

Answer 1

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

S₀ = 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);
}

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

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

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