Java recursion: Examples

I know how recursion works, that is:

Method calls itself until it reaches the base case, and then it can begin to solve its problem

In this code example is a method or removing flowers from a vase

I added a tracking statement to see how many flowers are in the vase after each call However, the output leaves seven flowers in the vase I'm confused why?

Code:

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

        System.out.println(flowersInVase);


    } else {
           // the vase is empty,nothing to do

    }
}

Call method:

public class RecursionPractice {

    public static void main(String[] args) {

        emptyVase(7);    
    }

Output:

1
2
3
4
5
6
7

Solution

In recursion, the order of calls is very important. When you expand it, you can better understand your own example It looks 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 the stack frame of emptyvase (1), the function execution is completed, so the current flowerinvase is printed, i.e. 1 Returns the previous stack frame and prints the currently stored variables each time until the last stack frame is reached

This is why the order is reversed! That's why if you change the print order and 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 result in:

7
6
5
4
3
2
1
0

The vase is actually empty, but because your condition is flowerinvase > 0, it means that when the last call is made with emptyvase (0), the else part will be executed and the value of the counter will not be printed there Add a print there and you'll see an empty vase

It's good to understand recursive methods (and examples) I think the important fact to pay attention to in your example is that a recursive call will interrupt the current function call and start a new call (execute the same function again), but the previous call will be remembered. Once the new call is completed, the process will continue to flow from the interrupted place!

You can think of each recursive call as the 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 the problem Recursion is quite expensive in memory allocation, and because the computer has a limited amount of memory, if too many boxes are created by recursion, the execution of the program reaches the maximum allowable number of boxes = stack frames and indicates stack overflow Please note that my explanation is very basic For a detailed explanation of the so-called call stack, take a look at this Wikipedia article – call stack