递归方法的困惑

java recursion

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

当我使用r.magic(3,11)时,我得到33的输出;如果我使用r.magic(2.25),则我得到50的输出,有人可以向我解释其背后的数学运算,因为我似乎并不真正使它有意义。

作者: user2879125 的来源 发布者: 2017 年 9 月 15 日

回应 2


1

506 作者的声誉

好的,这是。

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

这是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是从返回magic(a + a,b / 2)+ a调用。

因此,从函数返回时是堆栈,如果从1开始调用,它将简单地返回值,否则将添加一个带有返回值的a。

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。

如果您有任何疑问,可以发表评论。

作者: ABHISHEK HONEY 发布者: 2017 年 9 月 15 日

1

1579 作者的声誉

我想,您需要一些说明,而不是程序的步骤。这里是:

return magic(a + a, b / 2)

实际上是

return magic(2 * a, b / 2)

这意味着您将一个数字乘以2,然后将另一个数字除以2。因此,此操作不会更改Math的结果。

a * b =(2 * a)*(b / 2)

但是,您可以在这种方法中使用整数。偶数也可以。但是,如果将奇数除以2,则会丢失浮动部分“ 0.5”。

如果b为奇数,则说b = 2 * n + 1

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

递归地将这个额外的a变成2a,4a,...

您可以将a的这些倍数相加得出a * b。

当b为0时,这就是结束,不需要将a的任何倍数求和。

作者: Alperen 发布者: 2017 年 9 月 15 日
32x32