对于我在大学的离散结构类(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];
}
编辑:我解决了。谢谢大家的帮助!请看下面我的回答。
最佳答案
复发的定义有点奇怪。我会重写它:
S0 = 1
Si = Si-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()
代码的循环版本。
顺便说一句:您正在处理的重现实际上有一个封闭的形式:
Sn = (½)(n+1)(n+2)
关于java - 将迭代方法转换为递归方法 (Java),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18883696/