英文:
Why is the answer to this recursive function 8?
问题
这是一个我已经卡了一段时间的简单递归问题。基本上我明白 f(4) 如何返回 f(3) + f(3)，而这些会返回 f(2) + f(2) + f(2) + f(2)。然而，如果这些都被加在一起，答案岂不是大于 8？我对递归还很新，还在努力理解这个概念。
public class test{
public static int f(int n){
if(n <= 1){
return 1;
}
return f(n-1)+f(n-1);
}
public static void main(String[]args){
System.out.println(f(4));
}
}
英文:
This is a simple recursion problem that I've been stuck on for a while now. Basically I understand how f(4) would return f(3) + f(3), and these would return f(2) + f(2) + f(2) + f(2). However, if these are all being added together, wouldn't the answer be greater than 8? I am new to recursion and still trying to wrap my head around the concept.
public class test{
public static int f(int n){
if(n <= 1){
return 1;
}
return f(n-1)+f(n-1);
}
public static void main(String[]args){
System.out.println(f(4));
}
}
答案1
得分: 3
让我们从另一个角度来看待这个问题。
f(1) = 1
f(2) = f(1) + f(1) = 2
f(3) = f(2) + f(2) = 2 + 2 = 4
f(4) = f(3) + f(3) = 4 + 4 = 8
从中我们可以看出答案是8。如果你预期有一个不同的答案，你预期的是什么答案，并且你是如何得出那个答案的？
英文:
Let's look at this from the other direction.
f(1) = 1
f(2) = f(1) + f(1) = 2
f(3) = f(2) + f(2) = 2 + 2 = 4
f(4) = f(3) + f(3) = 4 + 4 = 8
From this, we can see the answer is 8. If you expected a different answer, what answer did you expect, and how did you arrive at that?
答案2
得分: 0
答案始终为 f(n) = 2^(n-1)
f(4) = 2^(4-1) = 2^3 = 8
英文:
The answer is always f(n) = 2^(n-1)
f(4) = 2^(4-1) = 2^3 = 8
答案3
得分: 0
将函数调用分成单独的语句可能会更容易看出。
public static void main(String[] args) {
System.out.println(f(4));
}
public static int f(int n) {
if (n <= 1) {
return 1;
}
int r = f(n - 1);
int s = f(n - 1);
System.out.println("(r + s) = " + (r + s));
return r + s;
}
输出结果：
(r + s) = 2
(r + s) = 2
(r + s) = 4
(r + s) = 2
(r + s) = 2
(r + s) = 4
(r + s) = 8
8
不同的人对不同的输出可能会有不同的反应，所以你可以根据自己的需要修改打印语句。通常，我发现理解任何程序的逻辑流程最有用的方法是将每个步骤的状态简单地写在纸上，并通过这种方式来逐步解析。
英文:
If you break up the calls into separate statements, it can be easier to see.
public static void main(String[] args) {
System.out.println(f(4));
}
public static int f(int n) {
if (n <= 1) {
return 1;
}
int r = f(n - 1);
int s = f(n - 1);
System.out.println("(r + s) = " + (r + s));
return r + s;
}
Prints
(r + s) = 2
(r + s) = 2
(r + s) = 4
(r + s) = 2
(r + s) = 2
(r + s) = 4
(r + s) = 8
8
Different people respond to different outputs so you can alter with your own print statements. I usually find the most useful way to understand logic flow for any program is to simply write down the state of each step on paper and work it thru that way.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论