短算法的试运行问题(递归)

Question

public class Algo{
    public static void main(String[] args){
        System.out.println(bar(4));
    }
    static int bar(int n){
        if(n==0 || n==1){
            return 1;
        }else{
            return n-bar(n-1);
        }
    }
}

因此，我相信上面的代码是这样做的：

n=4: 4-(4-1) = 4-3 = 1
n=3: 1-(3-1) = 1-2 = -1
n=2: -1-(2-1) = -1-1 = -2
n=1: Now we get into the if-statement, this basically means that bar(1) = 1, so in the end we have that -2-1 = -3

但是当我编译和运行它时，我得到了一个不同的输出，我不明白为什么。

Output: 2

我尝试了另一种算法，非常类似于这个算法(仅用乘法符号，也就是教员)，在这个模拟运行中，它已经成功了。但是这个算法似乎不起作用。

Answer 1

以下是它的计算方式：

bar(4) = 
4 - bar(3) = 
4 - (3 - bar(2)) = 
4 - (3 - (2 - bar(1))) = 
4 - (3 - (2 - 1))) 
4 - 3 + 2 - 1 = 
2

Answer 2

考虑到代码会递归到n-1，如果您按照增加n的顺序来考虑结果，那么就更容易了，因为您可以简单地在上一行的结果中替换。

n    working  result
====================
0    (by def) 1
1    (by def) 1
2    2-1      1
3    3-1      2
4    4-2      2

Answer 3

 bar(4) = 4 - bar(3) = 4 - 2 = 2
 bar(3) = 3 - bar(2) = 3 - 1 = 2
 bar(2) = 2 - bar(1) = 2 - 1 = 1
 bar(1) = 1