Reputation: 603

Recursive function prints something that I think it shouldn't

I believed that I have a good background in programming but today I came across something that made me question that. Here is the code:

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

}

In my opinion, this code shouldn't print anything. But it actually prints 1010 when I compile it. If the System.out.print(x % 2) was written before func(X/2), it would make sense but now it just looks not right. Any explanation on this?

Upvotes: 1

Answers (6)

Daniel Voina

Reputation: 3215

The behavior of printing ones and zeros is absolutely correct.

While your x>is strictly greater than 0 you will go deeper in recursion with a new x = int(x/2) because x is an integer.

When x<=1 you will have x/2==0 hence the recursion stops an you will start printing the remainders of x/2.

In your case:

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

HINT: When I do have this kind of problems I put System.out.println() traces in code in order to understand the flow. If you are using Eclipse/Netbeans/Idea you can go in debug mode and step in your code.

Upvotes: 1

Rohit Jain

Reputation: 213391

func(x/2);     ----------------> // Statement # 1
System.out.print(x % 2); ------> // Statement # 2

Statement # 2 would have been Unreachable Block had you returned the value of the func(x / 2) call at Statement # 1

Recursive function calls are stored on stack. So, for every invocation, a stack entry is made, storing the current call, and moving towards the next call.

Now, when your base condition is reached, stack starts to roll-back, by popping the previous state of the function, and then eventually it reaches where it started.

Now after every func call is popped from the stack, the execution continues with the next statement in the function where the last func() invocation was done (Statement # 2 in this case), and after completion, that function returns which in turns invokes next function on stack. (NOTE: - If you had return func(x / 2) in place of func(x / 2), then the code will not execute the next statement, but immediately give control to the next function in stack. Hence Unreachable Code)

Thus at last the statement

System.out.print(x % 2);

will get executed, when the stack is completely emptied, and the control returns to the

func(x / 2)

function call, which was at the bottom of the stack.

So, your recursion goes like this: -

Stack: -

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

Suppose x / 8 is the base condition. So, when the func(x / 8) completes execution, the next statement ot execute is: -

System.out.println(x % 2) -> Here value of x is original-x / 8

Then this function is popped from the stack, and returns the control to next function in the stack: - func(x / 4), which then executes the next statement : -

System.out.println(x % 2) -> Again x here is original-x / 4

And so-on. And then eventually, System.out.println(x % 2) is executed for original-x

Upvotes: 1

agaonsindhe

Reputation: 594

hmmmm At first glance I thought it won't print anything but tracing code gave me that 1010 is write answer as we are never changing x's value, I mean we are doing operations on x but we are storing.So that's why it is 1010 instead of nothing.

Good trick question

Upvotes: 0

Aniket Inge

Reputation: 25723

Its simple. At first, your function func() gets the value of 10. Internally it checks if 10 > 0. Since it is, it calls func(5/*10/2 = 5*/).

Then since 5 > 0, internally it calls func(2). This is because of truncation of .5. func(2/2 /*= 1*/) is called and that executes. That then, calls func(0), which returns. When it returns, the Print statement is executed with 1%2 = 1. That internally returns and the print statement is executed again with 2 % 2 = 0. Again it returns and print statement is executed again with arguments 5 % 2 = 1. Returning the last print statement executes printing 0 again.

Upvotes: 2