D.4.2

Describe the application of recursive algorithms.

Teaching Note:

Students should understand that recursion can be applied to a small subset of programming problems to produce elegant solutions. Students should also understand that recursive algorithms are rarely used in practice.

LINK Thinking abstractly, thinking recursively.

Sample Question:

sdfsdfsf

JSR Notes:

***** If used in 2020-21, with Topic 5, the dark grey highlighted sections are not so important.*****

Rationale for the depth of these notes

The thing is, with all of this, and particularly with the tracing assessment statements, if you are going to be able to truly spot and appreciate recursive situations, and if you are going to be able to trace recursive functions, you need to go a bit beyond both the Topic 5 and the OOP Extension assessment statements. You can't just dip into recursion to truly understand it, you have to truly understand it to truly understand it! So here goes!

Recursion Brief Intro.

Recursion is a way to iterate (to loop) without using the traditional for and while control structures. With recursion, repetition/iteration is accomplished by calling other instances of a the same method from within the method itself. You'll quite often hear recursion referred to as a method calling itself. But this is not actually true since what happens is new instances of the method are loaded into memory as the recursive "loop" progresses.

As the looping progresses, each instance of the method will be interrupted by a call to another instance of that method. And so on and so on. Eventually, one of the instances will reach its base case, and will not call another instance of the method, thus ending the iteration. From there, when that instance of the method is finished, the the flow of control goes back to the instance before which called it, and so on, up through the stack of yet unfinished instances, eventually getting back to the initial call, which also ends.

To appreciate this rather complex series of events, consider the following examples of recursive methods:

    public static void countDownToZero(int i){
        System.out.println(i);
        if (i > 0) { //The base case which, when we arrive at it we end.
            i--;
            countDownToZero(i);
        }
    }

If called as zeroToThree(4), this will print out:

4
3
2
1
0

Here is a variation of the above method that can count up from any number to any other number. So it will have to take two parameters, which is fine.:


public static void countingUp(int i, int j) {
        System.out.println(i);
        i++;
        if (i <= j) { //When this is false, we will have arrived 
                           //at the base case, and skip to return
            countingUp(i, j);
        }
        return
    }

So, if 15 and 18 were sent as parameters, the output would be:

15
16
17
18

Trace through it on paper or in your head. As you do so just remember that the i goes up each time, but the j stays the same in each instance.

A Little More on Base Case

The base case is the boundary value toward which any loop must move if it is to ever end. So even for loops and while loops have base cases; they are the situations at which the continue condition becomes false. Take the for loop in the next section for example; the base case is when i is not less than 4 - the loop ends at that base case.

With recursion, we think of the base case as being the call to the recursive function where finally there is some sort of resolution; we finally have "gotten to the bottom of it!", as the saying goes. For example in in the next section, the same as with the for loop, when i is not less than 4, we return from that recursive call. And taking another example, in a recursive binary search one base case is when we find the key.

In any recursive situation, we can say that all of the calls but one are recursive calls, and one and only one is the base case.

For, While, Do While, and Recursion All Accomplish Iteration

All three non-recursive looping control structures can accomplish the same kind of looping, though whiles should be used when the number of times a loop is to iterate is unknown. But recursion can do the same thing also. For example, the following two code segments accomplish the same output (assuming that in the case of zeroToThree, it is sent the parameter 0):

    public static void forLoopCountDown(){
        for(int i = 4; i > -1; i++){
            System.out.println(i);
        }
    }

So Why Recursion?

So if for loops and while and do while loops (i.e. "iterative" solutions) can accomplish looping, then why would we want to use recursion. Well, you could argue one reason it that it's cooler, but that's certainly not a great reason. Recursive solutions are usually way more inefficient than iterative versions, if they exist; just consider the memory efficiency penalty of having multiple large unfinished methods in memory all at the same time. So being "cooler" is not a reason to pick a recursive solution.

So even though recursive algorithms are rarely used in practice, here are three situations where we can usefully apply recursion. (Copied and pasted from 5.1.1.)

1. The recursive solution mirrors real life

In real life there are sometimes problems that are solved by solving a similar problem with a different set of values, and that problem, in turn, is solved by solving a similar problem with still different values, and so on,and so on, until an overall resolution is found. These are actual recursive situations, which therefore can, and should, have recursive solutions coded for them.

2. Recursive solutions are often more "elegant"

Recursive solutions often will be more elegant than their "iterative" counterparts, in that they take up a lot less lines of code. By choosing such a shorter, more elegant recursive solution, it often will be easier to read and follow. Though keep in mind that the reason this is possible goes back to reason 1; it mirrors the real life situation.

3. No iterative solution is possible

This is the case where you actually require recursion. Often times with such recursive solutions, there actually is no iterative solution. So that is the definitive reason to use a recursive solution: there is no other way to do so.

But also, why NOT recursion

From the Teaching Notes & Limitations of Recursion note that:

1. "Students should understand that recursion can be applied to a small subset of programming problems to produce elegant solutions."

2. "Students should also understand that recursive algorithms are rarely used in practice."

This is partly because recursion takes tons of system memory resources, since instance after instance after instance of a particular method is called, leading to potentially large stacks of un-finished recursive calls.You should never use recursion for the sake of using recursion - just to be fancy. Furthermore, it can be hard to follow, compared to simple iterative solutions.

Two Classic Recursive Examples Explained

The two standard algorithms in the IB CS curriculum that are recursive are the recursive binary search and traversals of binary trees. With both of them, if you think on an algorithmic level, you can see how they take the same strategy and apply it to smaller and smaller sub-divisions of the array. But whereas the binary search can be done, and done more efficiently the iterative way, the traversal of the binary tree cannot.

1. Recursive Binary Search

Even though there is an iterative approach to this, and we know it works well, in terms of looking at recursion, the recursive binary search is relatively easy to understand. To do a binary search in a recursive way, you repeat the following steps on smaller and smaller sub-arrays:

you look at the middle element,
and if what you are looking for is there, you are finished,
otherwise, you make that element the new low if the element you are looking for is larger than it, or the new high if the element you are looking for is smaller than it.
This exact same thing is done with each increasingly smaller sub array.

Here it is. (We'll look at it in detail later, buy for now, just try to see how it is recursive, in that it breaks down a big problem into smaller ones talked the same way.)

public static int recursiveBinarySearch(int[] arr, int low, int high, int key) {
    
    if (low < high) {
        int mid = low + (high - first) / 2; 
        if (key < sorted[mid]) {
            return recursiveBinarySearch(arr, low, mid-1, key);
            
        } else if (key > sorted[mid]) {
            return recursiveBinarySearch(arr, mid+1, high , key);
            
        } else {
            return mid;  
        }
    }
    return -1;  
}

2. (Recursive) Traversal of a Binary Tree

As is covered in Topic 5, a binary search tree is an Abstract Data Structure that has both the advantages of an array in that it is binarily searchable, and also the advantages of a list, in that elements can be added and deleted dynamically. So it really is an ideal data structure.

The only challenge a binary search tree presents is how to traverse it; i.e. how to visit all of the elements in its structure. Think about trying to visit all of the leaves in a real tree; how are you going to approach it, and in particular, how are you going to keep track of where you have already visited? So, in fact, no iterative approach on its own works. (Though you can enlist the help of a stack structure.)

You can't use a for loop, since it's a branching structure, and you can't simply go straight through... Well, recursion to the rescue!! What you can do is, from every branch, check left and right, and then check left and right from each of those and so on, and so on.

One thing, as is also covered in Topic 5 is there are three versions of the binary tree traversal: post, pre, an in-order.

Here's the pre-order traversal of a binary search tree recursive solution. Not only is it brief, and easy enough to read, keep in mind that there is no other straight-forward way to do it.

private String inOrderString = "";
private String traverseInOrder(StudentNode, String 2){
    if(p != null){
        traverseInOrder(p.getLeft(), inOrderString);
        inOrderString += p.getValue().getName();
        traverseInOrder(p.getRight(), inOrderString);
    }
    return inOrderString;
}

Here's an animation of the recursive traversal of a binary tree, remembering that it's the only real, appropriate, and necessary, application of recursion that we have seen/coded in the course.

Repeat of a basic example, like above, but with a step-by-step "trace through" below.

Though this is much better done live on the whiteboard.

Consider the following recursive method:

1.   public static void zeroToThree(int i) {        
2.            System.out.println(i);        
3.             i++;        
4.             if (i < 4) { //The base case which, when we arrive at it 
5.                              //being false, no more recursion will be needed            
6.                 zeroToThree(i);         
7.             }
8.             return;  
9.   }

If called as zeroToThree(0), this will print out:

0
1
2
3

Now, Step-by-Step

What follows is a line-by-line explanation of what happens, from the example above. So fasten your safety belt, and take it one step at a time:

First Instance:

The first instance of the zeroToThree( ) will first print out 0 at line #2. This is because 0 is what i is in this particular instance, since 0 is what was inititally sent as a parameter to the initial call, say from the main() method.

Output so far:
0

The next line of the method has i go up by one, so in this case from 0 to 1. With the next line, line #4, the condition if(i < 4) evaluates to true, so another instance of zeroToThree is called. (Though note that the first instance of zeroToThree is still in memory, unfinished, since it has not yet reached the last brace of itself.)

First Instance Interrupted and placed on the unfinished stack. Second Instance Called:

As the second instance of zeroToThree() starts, its variable i, which has been passed to it, will be printed - so another line of output; this time 1.

Output far:
0
1

The i then goes up to 2, which is still less than 4, so a third instance of zeroToThree is called (and this second instance of zeroToThree is also left in an un-finished state).

Second Instance Interrupted and placed on the unfinished stack. Third Instance Called:

So then the third instance of zeroToThree starts, and prints out what it was sent, which is 2.

Output so far:
0
1
2

And as in the other instances, i goes up by one, so this time to 3, and 3 is less than 4, so a fourth instance of zeroToThree is called (and this third instance of zeroToThree left unfinished like the previous two instances of the method).

Third Instance Interrupted and placed on the unfinished stack. Fourth Instance Called:

The fourth instance of zeroToThree receives 3 as its parameter, so with its first line, 3 is printed out.

Output so far:
0
1
2
3

Then i goes up to 4, and for the first time in this sequence of execution, the loop control condition is not met, since 4 is not less than 4. **This is the base case; i.e. the case with which "an answer" is easily found, and there is no need to call another instance of the function recursively.**

So this particular instance of zeroToThree by-passes making another call to another instance of zeroToThree, and instead easily finishes off and so is garbage collected out of memory.

Fourth instance of zeroToThree ends.

And this is the point where all of the instance end, one at a time, from the last one called on up to the first one called - it may make your head spin a bit, but give it a go.

Since that call, which was made in the third call to zeroToThree, is finished, the third call to zeroToThree can also be finished.

Third instance of zeroToThree ends and is popped off the stack.

And since the third call to zeroToThree is finished, the method which called it - the second instance of zeroToThree, can finish.

Second instance of zeroToThree ends and is popped off the stack.

And since the second call to zeroToThree is finished, what called it - the first call to zeroToThree, can also finish.

First (original) instance of zeroToThree ends and is popped off the stack.

And that's it for zeroToThree(0).