More Recursion

Double Recursion

Introduction

Recursion is a wonderful thing once you've mastered it. There are often problems in Computer Science that have simple, concise solutions once recursion is applied to the problem. One of the biggest problem for beginners occurs when they try to follow the recursive calls of a routine that makes two or more calls to itself. The problem becomes evident in what I term a double recursion. Once you understand how to trace the calls in this type of routine you will be able to apply the analysis to any number of calls.

What exactly is a double recursion? It's a method that calls itself twice. This is different from a method that chooses one type of recursive call over another. In this case every call to the method will spawn 2 more calls to the method. This then recurses down spawning 2 more calls until the test case is met and the method calls start to return back up the chain. The problem for the beginning student is that this type of arrangement maps out a 'tree' of calls and the student must perform a manual 'depth' first search of the call tree.

Trees

Trees are a data structure object that crop up in computer science and while it is not necessary to program one for the AP Computer Science exam a brief description of terminology for trees is useful to the discussion here. Students when trying to figure out a double recursion forget about what the computer is doing and bounce back and forth between a 'depth' first search of the method calls and what is know as a 'breadth' first search.

A diagram will explain this much better than words.

Depth First Search

In a depth search first you must follow the branches all the way down then go back up and follow any other branches etc. The numbering of the boxes shows how we visit the nodes. This is the same for recursion when 2 or more recursive calls are made. You must follow the first recursive trail and then back up and follow the next call in a similar fashion to this tree.

Breadth First Search

The mistake is to try to account for both calls at the same time when you enter the first call sequence. The computer doesn't do it this way it blindly follows the trail of the first call then when it comes back it handles the second. So breadth first search is a mistake of reading the program as you would a story. You complete the paragraph then go off to see what the next sequence is. The following diagram is the WRONG way to follow a recursion tree:

I almost don't want to show you this for fear you will worry about it. But rememeber you must follow the first call sequence down until the test case is reached. Then you pop back up at each stage to handle the second call. Forget about breadth first and stick to the order of the first diagram. Recursion is naturally a depth first search.

Make the computer do it

While you must learn to draw out the call structure by hand. There is no reason not to experiment with having the computer do it for you. With the appropriate use of output statements and a little bookkeeping in a program example we can make the computer account for how the recursion is happening. First let's create a single recursive method that logs it's calls then we can add a double recursion to the example. In the end you will have a program that maps out it's call tree in a textual representation. From there you only need to be able to draw a sketch on the test and you should be ready for any recursive problem thrown at you.

class DoubleRecurse {

    public static void singleRecursion(int[] vals, int m) {
        if (m >= 0) {
            System.out.print(vals[m] + "  ");
            singleRecursion(vals, m - 1);
        }
    }

    public static void main(String[] args) {
        int[] myArray = {5, 4, 3, 2, 1, 0};

        singleRecursion(myArray, myArray.length-1);
        System.out.println();
    }
}

Output

run:
0  1  2  3  4  5  
BUILD SUCCESSFUL (total time: 0 seconds)

So the code goes to the end of the array and prints each value. This reverses the order of the array. This is because the print happens before the recursive call back into singleRecursion. If the print statement is moved to after the method call the recursion goes all the way to m = -1 which ends the recursion then as the computer starts to come back up from it's decent into the recursion values will be printed in normal order indexed from 0 - 5 to print the values as they appear in the intialization of myArray.

Here is the class with the print statement moved after the recursive call:

class DoubleRecurse {

    public static void singleRecursion(int[] vals, int m) {
        if (m >= 0) {
            singleRecursion(vals, m - 1);
            System.out.print(vals[m] + "  ");
        }
    }

    public static void main(String[] args) {
        int[] myArray = {5, 4, 3, 2, 1, 0};

        singleRecursion(myArray, myArray.length-1);
        System.out.println();
    }
}

Output 1

run:
5  4  3  2  1  0  
BUILD SUCCESSFUL (total time: 1 second)

Exposing Recursion

Let's add some print statements to expose the recursion more explicitly in the output. One way to display the recursion is to present the output from each call on a separate line. By using field variables we can also track the number of calls and the depth (or level) of the recursion. The depth field can be used to prepend spaces so that deeper levels of recursion are indented in the output.

The changes will include making this object oriented by taking away the static method and making it a plain method call to singleRecursion. This will mean that a DoubleRecurse object needs to be instantiated in the main method so the method can be used. But it means that the new fields will be available for any new recursive methods added to the class. The new code with the tracking fields and the new output statements follows:

class DoubleRecurse {
    // Track number of calls
    int calls = 0;
    // Track level
    int depth = 0;

    void indent(int spaces)
    {
        for (int i = 0; i < spaces; i++) {
            System.out.print("  ");
        }
    }

    public void singleRecursion(int[] vals, int m) {
        calls++;
        depth++;

        // track calls depth and m
        indent(depth);
        System.out.println("calls = " + calls 
                + "  depth = " + depth 
                + "  m = " + m);

        if (m >= 0) {
            singleRecursion(vals, m - 1);
            indent(depth);
            System.out.println(vals[m]);
        }
        else {
            indent(depth);
            System.out.println("test case met no more recursion start backing out");
        }

        depth --;
    }

    public static void main(String[] args) {
        DoubleRecurse recursion = new DoubleRecurse();
        int[] myArray = {5, 4, 3, 2, 1, 0};

        recursion.singleRecursion(myArray, myArray.length-1);
        System.out.println();
    }
}

Output 2

run:
  calls = 1  depth = 1  m = 5
    calls = 2  depth = 2  m = 4
      calls = 3  depth = 3  m = 3
        calls = 4  depth = 4  m = 2
          calls = 5  depth = 5  m = 1
            calls = 6  depth = 6  m = 0
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
          4
        3
      2
    1
  0

BUILD SUCCESSFUL (total time: 0 seconds)

Double Recursion

Now that there are tools to display the recursive calls, the program can be modified to track a doubly recursive call. Rather than change the singleRecursion method a new method called doubleRecursion can be added.

In the new code there are 4 method calls. The original singleRecursion method that does no tracking. A new method called singleRecursionTrack that has the tracking fields and output statements. Then the single recursion modified to do double recursion and it's tracking counterpart named doubleRecursion and doubleRecursionTrack respectively

class DoubleRecurse {
    // Track number of calls
    int calls = 0;
    // Track level
    int depth = 0;

    void indent(int spaces)
    {
        for (int i = 0; i < spaces; i++) {
            System.out.print("  ");
        }
    }

    public void singleRecursion(int[] vals, int m) {        
        if (m >= 0) {
            singleRecursion(vals, m - 1);
            System.out.print(vals[m] + "  ");
        }
    }

    public void singleRecursionTrack(int[] vals, int m) {
        this.calls++;
        this.depth++;

        // track calls depth and m
        indent(this.depth);
        System.out.println("calls = " + this.calls 
                + "  depth = " + this.depth 
                + "  m = " + m);

        if (m >= 0) {
            singleRecursionTrack(vals, m - 1);
            indent(this.depth);
            System.out.println(vals[m]);
        }
        else {
            indent(this.depth);
            System.out.println("test case met no more recursion start backing out");
        }

        this.depth--;
    }

    public void doubleRecursion(int[] vals, int m) {        
        if (m >= 0) {
            this.doubleRecursion(vals, m - 1);
            System.out.print(vals[m] + "  ");
            this.doubleRecursion(vals, m - 3);
        }
    }

    public void doubleRecursionTrack(int[] vals, int m) {
        this.calls++;
        this.depth++;

        // track calls depth and m
        indent(this.depth);
        System.out.println("calls = " + this.calls 
                + "  depth = " + this.depth 
                + "  m = " + m);

        if (m >= 0) {
            this.doubleRecursionTrack(vals, m - 1);
            indent(this.depth);
            System.out.println(vals[m]);
            this.doubleRecursionTrack(vals, m - 3);
        }
        else {
            indent(this.depth);
            System.out.println("test case met no more recursion start backing out");
        }

        this.depth --;
    }


    public static void main(String[] args) {
        DoubleRecurse recursion = new DoubleRecurse();
        int[] myArray = {5, 4, 3, 2, 1, 0};

        recursion.singleRecursion(myArray, myArray.length-1);
        System.out.println();
        recursion.singleRecursionTrack(myArray, myArray.length-1);
        System.out.println();
        recursion.calls = 0;  // start new recursion reset calls to track
        recursion.doubleRecursion(myArray, myArray.length-1);
        System.out.println();
        recursion.doubleRecursionTrack(myArray, myArray.length-1);
        System.out.println();
    }
}

Output 3

run:
5  4  3  2  1  0  
  calls = 1  depth = 1  m = 5
    calls = 2  depth = 2  m = 4
      calls = 3  depth = 3  m = 3
        calls = 4  depth = 4  m = 2
          calls = 5  depth = 5  m = 1
            calls = 6  depth = 6  m = 0
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
          4
        3
      2
    1
  0

5  4  3  2  5  1  5  4  0  5  4  3  
  calls = 1  depth = 1  m = 5
    calls = 2  depth = 2  m = 4
      calls = 3  depth = 3  m = 3
        calls = 4  depth = 4  m = 2
          calls = 5  depth = 5  m = 1
            calls = 6  depth = 6  m = 0
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
              calls = 8  depth = 7  m = -3
              test case met no more recursion start backing out
          4
            calls = 9  depth = 6  m = -2
            test case met no more recursion start backing out
        3
          calls = 10  depth = 5  m = -1
          test case met no more recursion start backing out
      2
        calls = 11  depth = 4  m = 0
          calls = 12  depth = 5  m = -1
          test case met no more recursion start backing out
        5
          calls = 13  depth = 5  m = -3
          test case met no more recursion start backing out
    1
      calls = 14  depth = 3  m = 1
        calls = 15  depth = 4  m = 0
          calls = 16  depth = 5  m = -1
          test case met no more recursion start backing out
        5
          calls = 17  depth = 5  m = -3
          test case met no more recursion start backing out
      4
        calls = 18  depth = 4  m = -2
        test case met no more recursion start backing out
  0
    calls = 19  depth = 2  m = 2
      calls = 20  depth = 3  m = 1
        calls = 21  depth = 4  m = 0
          calls = 22  depth = 5  m = -1
          test case met no more recursion start backing out
        5
          calls = 23  depth = 5  m = -3
          test case met no more recursion start backing out
      4
        calls = 24  depth = 4  m = -2
        test case met no more recursion start backing out
    3
      calls = 25  depth = 3  m = -1
      test case met no more recursion start backing out

BUILD SUCCESSFUL (total time: 0 seconds)

This gives a good trail of when calls take place and at what level but it is still not completely obvious when the first recursive call is taking place and when the second is. By adding a field to the doubleRecursion the call number can be saved separately from the total calls. Adding 2 printlns before the calls (indenting for the current depth of course) now highlights exactly where the processing is being done.

public void doubleRecursionTrack(int[] vals, int m) {
    int current_call = 0;

    this.calls++;
    current_call = this.calls;
    this.depth++;

    // track calls depth and m
    indent(this.depth);
    System.out.println("calls = " + this.calls 
            + "  depth = " + this.depth 
            + "  m = " + m);

    if (m >= 0) {
        indent(this.depth);
        System.out.println("call = " + current_call + " enter first recursion");
        this.doubleRecursionTrack(vals, m - 1);
        indent(this.depth);
        System.out.println(vals[m]);
        indent(this.depth);
        System.out.println("call = " + current_call + " enter second recursion");
        this.doubleRecursionTrack(vals, m - 3);
    }
    else {
        indent(this.depth);
        System.out.println("test case met no more recursion start backing out");
    }

    this.depth --;
}

Output 3

run:
5  4  3  2  1  0  
  calls = 1  depth = 1  m = 5
    calls = 2  depth = 2  m = 4
      calls = 3  depth = 3  m = 3
        calls = 4  depth = 4  m = 2
          calls = 5  depth = 5  m = 1
            calls = 6  depth = 6  m = 0
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
          4
        3
      2
    1
  0

5  4  3  2  5  1  5  4  0  5  4  3  
  calls = 1  depth = 1  m = 5
  call = 1 enter first recursion
    calls = 2  depth = 2  m = 4
    call = 2 enter first recursion
      calls = 3  depth = 3  m = 3
      call = 3 enter first recursion
        calls = 4  depth = 4  m = 2
        call = 4 enter first recursion
          calls = 5  depth = 5  m = 1
          call = 5 enter first recursion
            calls = 6  depth = 6  m = 0
            call = 6 enter first recursion
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
            call = 6 enter second recursion
              calls = 8  depth = 7  m = -3
              test case met no more recursion start backing out
          4
          call = 5 enter second recursion
            calls = 9  depth = 6  m = -2
            test case met no more recursion start backing out
        3
        call = 4 enter second recursion
          calls = 10  depth = 5  m = -1
          test case met no more recursion start backing out
      2
      call = 3 enter second recursion
        calls = 11  depth = 4  m = 0
        call = 11 enter first recursion
          calls = 12  depth = 5  m = -1
          test case met no more recursion start backing out
        5
        call = 11 enter second recursion
          calls = 13  depth = 5  m = -3
          test case met no more recursion start backing out
    1
    call = 2 enter second recursion
      calls = 14  depth = 3  m = 1
      call = 14 enter first recursion
        calls = 15  depth = 4  m = 0
        call = 15 enter first recursion
          calls = 16  depth = 5  m = -1
          test case met no more recursion start backing out
        5
        call = 15 enter second recursion
          calls = 17  depth = 5  m = -3
          test case met no more recursion start backing out
      4
      call = 14 enter second recursion
        calls = 18  depth = 4  m = -2
        test case met no more recursion start backing out
  0
  call = 1 enter second recursion
    calls = 19  depth = 2  m = 2
    call = 19 enter first recursion
      calls = 20  depth = 3  m = 1
      call = 20 enter first recursion
        calls = 21  depth = 4  m = 0
        call = 21 enter first recursion
          calls = 22  depth = 5  m = -1
          test case met no more recursion start backing out
        5
        call = 21 enter second recursion
          calls = 23  depth = 5  m = -3
          test case met no more recursion start backing out
      4
      call = 20 enter second recursion
        calls = 24  depth = 4  m = -2
        test case met no more recursion start backing out
    3
    call = 19 enter second recursion
      calls = 25  depth = 3  m = -1
      test case met no more recursion start backing out

BUILD SUCCESSFUL (total time: 2 seconds)

Conclusion

This should help when trying to follow recursion. Certainly in an exam situation they don't allow an IDE to code with, but with some paper, pencil and a little fortitude even the average student should be able to build a recursion tree by hand. The AP question makers understand there is limited time so the example provided here is much more complex in terms of the number of calls a student will have to track.

A study recommendation
If you find yourself getting the recursion problems wrong in your practice tests, code them up with indentation and tracking information. Most likely you are making a simple mistake drawing out the call tree. The output from your code should enlighten you on the proper call pattern.

Date: 2013-03-26T16:55-0400

Author: Nasty Old Dog