CODEWITHSUNDEEP
javarecursion
Vikki Nayyar
Vikki Nayyar

Reputation: 29

How does 1 2 3 come at the end?

In this program, if the user enters the number 3, the o/p will be 3 2 1 1 2 3 , I understood how 3 2 1 came, but I didn't understand how 1 2 3 came at the end. 

class GFG{ 
static void printFun(int test) 
{ 
    if (test < 1) 
        return; 
    else
    { 
        System.out.printf("%d ",test); 
        printFun(test-1); // statement 2 
        System.out.printf("%d ",test); 
        return; 
    } 
} 

public static void main(String[] args) 
{ 
    int test = 3; 
    printFun(test); 
} 
}

Upvotes: 3

Views: 607

Answers (5)

nits.kk
nits.kk

Reputation: 5336

Function calls are maintained by stack. All local variables of the function corresponds to the function call instance. Each function call instance is maintained in Stack.

Statement above Recursive call is a PUSH operation and after recursive call is POP operation.

Hence its (Statement before recursive call)

print(3) PUSH(3), print (2) PUSH(2), print(1) PUSH(1)

followed by (Statement after recursive call).

POP(1) print(1), POP(2) print(2) , POP(3) print(3)

Hence output is 3 2 1 1 2 3

Upvotes: 0

davidxxx
davidxxx

Reputation: 131486

The recursive invocation printFun(test-1) make the method goes on to invoke it in this way :

printFun(3); // original
printFun(2);
printFun(1);
printFun(0);

Arriving at this time it doesn't perform any other recursive call because of the condition encountered for printFun(0).
The current call that is the last recursive call (printFun(0)) goes on with return. Then the execution goes up to the caller of printFun(0) that is printFun(1) that executes the second System.out.printf("%d ",test); statement and it returns.
Then same logic : The execution goes up to the method that invoked that, that is printFun(2).
And that goes on to go up until the initial one invocation.

You can see calls in this way :

printFun(3)
   printFun(2)
      printFun(1)
          printFun(0)
                   -- No more recursive call, execution goes on where we are
          printFun(0)
      printFun(1)
   printFun(2)
printFun(3)

Upvotes: 3

Sweeper
Sweeper

Reputation: 273380

One way to trace through recursive functions is by expanding every recursive call, like a math expression.

First we start with

printFun(3)

That expands to:

print(3) // I have shortened System.out.printf here to just "print" to remove the noise
printFun(2)
print(3)

We still have a recursive call (printFun(2)), so let's expand that.

print(3)
print(2)
printFun(1)
print(2)
print(3)

Continue expanding:

print(3)
print(2)
print(1)
printFun(0)
print(1)
print(2)
print(3)

And one last time (since printFun(0) doesn't do anything, we just remove it):

print(3)
print(2)
print(1)
print(1)
print(2)
print(3)

Oh look! That will produce the output 3 2 1 1 2 3!

Upvotes: 4

isstiaung
isstiaung

Reputation: 611

I added some print commands to help you understand this.

class GFG{
    static int count = 1;  
    static String combined = "";
    static void printFun(int test){ 
        System.out.println("No of times Function printFun has been called : " + count);
        count = count + 1;
        if (test < 1)
            return;
        else{
            System.out.println("Adding " + test + " to combined string");
            combined = combined + test;
            printFun(test-1); // statement 2 
            System.out.println("Returning to the previous call of printFun");
            combined = combined + test;
            System.out.println("Adding " + test  + " to combined string");
            return;
       }
    } 
    public static void main(String[] args){ 
        int test = 3;
        printFun(test);
        System.out.println(combined);
    }
}

I'm printing out the combined string at the end, the print statements should indicate how the function gets recursively called.

Upvotes: 2

Melvin
Melvin

Reputation: 1041

Ok - nature of recursions. Recursions put their calls on stacks which is built bottom-up. Whenever a member is recalled from the stack it is to be taken from the top till we reach the bottom again. Lets go through it line-per-line:

function is called 1st time with 3

function writes: 3 and calls itself with 2 - function halts (right after statement2) and waits for execution

function writes: 2 and calls itself with 1 - function halts and waits for execution

function writes: 1 and calls itself with 0 - call returns immediately because of value 0. Time to reduce the caller-stack and continue halted functions.

last function halt is reactivated (it was 1) and writes: 1 - then function returns

last function halt is reactivated (it was 2) and writes: 2 - then function returns

last function halt is reactivated (it was 3) and writes: 3 - then function returns

program stops.

Therefore you get the line of numbers you wrote.

Upvotes: 3

Related Questions