Java Recursion: Example

In recursion the order of the calls is very important! You can understand better your own example when you unroll it. It will look like this:

// step 1
// flowerInVase is greater than 7, so the first thing to do is call the function again! 
// Note that the System.out.println is NOT yet reached because of the execution of the function!
// call emptyVse(7 - 1), the *stack* has *remembered* to the current value of *floweInVase* => 7
emptyVase(7); 
// step 2
emptyVase(6);
// condition is *true* yet again, so the same rules as above apply
// current *remembered* value of `floweInVase` is 6
// step 3
emptyVase(5);
// and so on ... until `flowerInVase` is 0 ... now ...

Now the stack looks like this:

emptyVase(7)
    emptyVase(6)
        emptyVase(5)
            emptyVase(4)
                emptyVase(3)
                    emptyVase(2)
                        emptyVase(1)
                            emptyVase(0) 
                                -> nothing to do, recursion is stopped.
                                -> so go back to previous 
                                -> *stack frame* which is 1
                        System.out.println(1);
                    System.out.println(2);
                System.out.println(3);
            System.out.println(4);
        System.out.println(5);
    System.out.println(6);
System.out.println(7);

In stack frame for emptyVase(1) the function execution is done, so print the current flowerInVase which is 1. Go back to the previous stack frame, every time print the currently stored variable until the last stack frame is reached.

And that is why the order is reverse! That is also why if you change the order of the print and the function execution it will look as expected.

public static void emptyVase( int flowersInVase ) {
    // if there is a flower to take from the vase
    if( flowersInVase > 0 ) {
        // print the count of flowers BEFORE one is taken!
        System.out.println(flowersInVase);
        // take one flower and put it aside
        emptyVase( flowersInVase - 1 ) ;
    } else {
           // the vase is empty, nothing to do
           System.out.println(flowersInVase);
           // print 0!
    }
}

This will produce:

7
6
5
4
3
2
1
0

The vase is actually empty, but because your condition is flowerInVase > 0, this means when the last call is made with emptyVase(0) the else part is taken and you don't print there the value of the counter. Add a print there and you will see an empty vase.

Your approach (and the example) for understanding recursion is good. I think the important thing to notice in your example is the fact, that the recursive call interrupts the current function call and starts a new one (executes the same function again), but the previous call is remembered and once the new call is done, the flow continues from where it was interrupted!

You could imagine every recursive call as a creation of a box in a box:

|-------------------------------|
|--- emptyVase(7)           --- |
|                               |
|   |--- emptyVase(6)       ---||
|   |                          ||
|   |   |--- emptyVase(5)   ---||
|   |   |                      ||
|   |   |   |... and so on     ||
|   |   |   |---emptyVase(0)---||
|   |   |   | S.out.println(0) ||
|   |   |   |------------------||
|   |   |----------------------||
|   |   System.out.println(6)  ||
|   |--------------------------||
|   System.out.println(7);     ||
|-------------------------------|

The deeper the recursion, the more boxes you have.

This is also where the problem is. Recursion is pretty expensive in terms of memory allocation and because the computers have a finite amount of memory, if the recursion creates too many boxes, the execution of the program reaches the maximum allowed count of boxes = stack frames and says stack overflow. Be aware that my explanation is a very basic one. For a thorough explanation of the so called call stack have a look at this Wikipedia article - Call stack.

Each call to emptyVase() will print a flowersInVase value , so basicly you will call System.out.println() 7 times. The first print '1' is for the last call to emptyVase(), the second one '2' is for the before last one and so again .The last one '7' is for the first call to emptyVase() witch was realy 7 flower in the vase.

Nopes. The method is fine. It will keep on removing one flower at a time from the vase till the vase is empty. If you are expecting the below output(assuming that the method is called with flowersInVase to be 10 ):

10 9 8 7 6 5 4 3 2 1

Then you should write System.out.println(flowersInVase); emptyVase( flowersInVase - 1 ); instead of emptyVase( flowersInVase - 1 ); System.out.println(flowersInVase);

try it with an int[] instead (only copy and pasted your code and substituted the array for the int -- you'll have to verify it works)

public static void emptyVase( int[] flowersInVase ) {
      if( flowersInVase[0] > 0 ) {
       // take one flower and
        emptyVase( flowersInVase[0]-- ) ;

        System.out.println(flowersInVase[0]);

      } 
    }

...

public class RecursionPractice {

public static void main(String[] args) {

    emptyVase(new int[]{7});

}

The reason it won't work with a primitive int is because only the value of the int is passed, not a reference to the memory location holding the value, which is what you need to have in order to have the change reflected in all method invocations.

Print the flowersInVase before the recursive call. That will solve your confusion like below.

public static void emptyVase( int flowersInVase ) {
          if( flowersInVase > 0 ) {
           // take one flower and


            System.out.println(flowersInVase);  // **** Moved the print Here **********


            emptyVase( flowersInVase - 1 ) ;




          } else {
           // the vase is empty, nothing to do
              System.out.println("Hurray It's empty now..");
          }
        }



public class RecursionPractice {

    public static void main(String[] args) {

        emptyVase(7);
    }