java - 递归方法困惑

Question

鉴于以下情况

public class Recursion {
    public static int magic(int a, int b) {
        if (b == 0) {
            return 0;
        } else {
            if (b % 2 == 0) 
              return magic(a + a, b / 2);
            else
              return magic(a + a, b / 2) + a;
        }
    } 

    public static void main(String[] args) {
        Recursion r = new Recursion();
        System.out.println(r.magic(3,11));
      //System.out.println(r.magic(2,25));
    }
}

当我使用 r.magic(3,11) 时，我得到的输出为 33，如果我使用 r.magic(2.25) ，我得到的输出为 50，有人可以向我解释其背后的数学吗，因为我可以'似乎真的没有道理。

Answer 1

好的，就到这里了。

首先你需要了解递归的基础知识，比如它如何返回值以及退出条件是什么。

这是 2 和 25 的堆栈跟踪。在递归中，我们创建一个堆栈，这是 2 和 25 的堆栈。a 和 b 的第一个调用值位于堆栈底部。即(2,25)。您只需要像这样想象它。

a  b    called from return magic(a+a,b/2) or return magic(a+a,b/2)+a
64 0
32 1    2
16 3    2
8  6    1
4 12    1
2 25    2

这里 1 用于从 magic(a+a,b/2) 调用，2 用于从 return magic(a+a,b/2)+a 调用。

因此，从这里的函数返回时是堆栈。如果从 1 调用它，那么它将简单地返回值，否则它将添加一个带有返回值的值。

a  b
64 0        returns 0
32 1    2   returns 32
16 3    2   returns 32+16
8 6     1   returns 32+16
4 12    1   returns 32+16
2 25    2   returns 32+16+2

So the final return statement returns 50

对于第二次调用，类似地，这里是堆栈跟踪。

a  b
48 0        returns 0
24 1    2   returns 24
12 2    1   returns 24
6 5     2   returns 24+6
3 11    2   returns 24+6+3

So the final return statement returns 33

现在您可以看到结果是 50 和 33。

如有疑问可以评论。