### 递归方法的困惑

186 观看

2回复

41 作者的声誉

``````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));
}
}
``````

### 回应 (2)

1

506 作者的声誉

``````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
``````

``````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
``````

1

1579 作者的声誉

``````return magic(a + a, b / 2)
``````

``````return magic(2 * a, b / 2)
``````

a * b =（2 * a）*（b / 2）

a *（2 * n + 1）=（2 * a）*（（2 * n + 1）/ 2）

2 * a * n + a =（2 * a）*（n + 0.5）

2 * a * n + a = 2 * a * n + a

2 * a * n + a = 2 * a * n