1

我相信我在编程方面有很好的背景，但今天我遇到了一些让我质疑的事情。这是代码：

public class Recursive{
public static void main(String[] args) {
    func(10);        
}

static void func(int x)
{
    if(x > 0) 
    {
        func(x/2);
        System.out.print(x % 2);     // I thought the code won't reach here ever
    }                
}

}

在我看来，这段代码不应该打印任何东西。但是1010当我编译它时它实际上会打印出来。如果System.out.print(x % 2)是以前写的func(X/2)，那是有道理的，但现在看起来不对。对此有何解释？

4

6 回答 6

2

调用 func 然后打印 x%2。

另一方面，如果您使用 return func(x/2)，则永远无法到达 print 语句。

于 2012-10-18T11:47:16.117 回答
2

这很简单。首先，您的函数 func() 获取值 10。它在内部检查 10 > 0。既然是，它调用 func(5 /*10/2 = 5*/)。

然后由于 5 > 0，它在内部调用 func(2)。这是因为 0.5 的截断。 func(2/2 /*= 1*/)被调用并执行。然后，调用 func(0)，它返回。当它返回时，以 1%2 = 1 执行 Print 语句。内部返回，并以 2 % 2 = 0 再次执行 print 语句。它再次返回并以参数 5 % 2 = 1 再次执行 print 语句。返回最后一个打印语句会再次执行打印 0。

于 2012-10-18T11:51:44.943 回答
1

它必须对 func 进行第二次调用，然后第一次调用已经完成，它将沿着堆栈向下工作以完成原始函数。

您需要查找基本的递归理论。

http://en.wikipedia.org/wiki/Recursion_(computer_science )。

如上所述，使用 return func(x/2) 将从堆栈中删除该函数，因此永远不会到达函数的末尾。

于 2012-10-18T11:49:41.500 回答
1 
func(x/2);     ----------------> // Statement # 1
System.out.print(x % 2); ------> // Statement # 2

Statement # 2如果您返回atUnreachable Block的值，将会是func(x / 2) callStatement # 1

Recursive function calls存储在stack. 因此，对于每次调用，stack entry都会进行 a，存储当前调用，然后进行下一次调用。

现在，当您的基本条件达到时，通过弹出函数的先前状态stack开始roll-back，然后最终到达它开始的位置。

现在，在func从堆栈中弹出每个调用之后，执行将function在最后一次func()调用完成的地方继续执行下一条语句(Statement # 2 in this case)，完成后，该函数返回，该函数依次调用堆栈上的下一个函数。（注意： - 如果你有return func(x / 2)代替func(x / 2)，那么代码将不会执行下一条语句，而是立即将控制权交给堆栈中的下一个函数。因此Unreachable Code）

因此最后声明

System.out.print(x % 2);

将被执行，当stack完全清空时，控制权返回到

func(x / 2)

函数调用，位于堆栈的底部。

所以，你的递归是这样的： -

堆栈： -

func(x / 8)  --> Base condition
func(x / 4)  ^
func(x / 2)  ^
func(x)      --> First invocation

假设x / 8是基本条件。因此，当func(x / 8)完成执行时，执行的下一条语句是：-

System.out.println(x % 2)-> 这里 x 的值为original-x / 8

然后这个函数从堆栈中弹出，并将控制权返回给堆栈中的下一个函数： - func(x / 4)，然后执行下一条语句： -

System.out.println(x % 2)->x这里又是original-x / 4

等等。然后最终，System.out.println(x % 2)被执行original-x

于 2012-10-18T12:01:29.790 回答
1

打印一和零的行为是绝对正确的。

虽然您的 x> 严格大于 0，但您将使用新的 x = int(x/2) 进行更深入的递归，因为 x 是一个整数。

当 x<=1 时，您将获得 x/2==0，因此递归停止，您将开始打印 x/2 的剩余部分。

在你的情况下：

f(10)->f(5)->f(2)->f(1)->f(0)  
                          |
  0 <-  1  <- 0  <-  1  <-+

提示：当我确实遇到此类问题时，我会将 System.out.println() 跟踪代码放入代码中以了解流程。如果您使用的是 Eclipse/Netbeans/Idea，您可以进入调试模式并单步执行您的代码。

于 2012-10-18T12:39:10.197 回答
0

嗯，乍一看，我以为它不会打印任何东西，但跟踪代码给了我 1010 是写答案，因为我们永远不会改变 x 的值，我的意思是我们正在对 x 进行操作，但我们正在存储。所以这就是为什么它是 1010什么都没有。

好技巧问题

于 2012-10-18T12:04:23.787 回答