Logout

Recursion

(Note that the first two paragraphs and the first example are a repeat from the "Revolution" part of Java Revolution.)

Recursion is a way to iterate (to loop) without using the traditional for and while control structures. With recursion, multiple iterations blocks of code are 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 with all loops, it is important to have a way for the loop to end. But since it is multiple instances of the method, it cannot be one variable which stops all instances of the method, rather, the "Loop Control Variable" of each instance will have to look after ending its own instance. But the problem is that each instance of the method will have to wait for the call to the other instance to end, and that instance in turn needs to wait for the instance that it called to end, and so on. So sooner or later one of the instances that is called will have to end before making another call. Then all of the other instances of the method on up the line can end one at a time. To appreciate this rather complex series of events, consider the following example of a recursive method:


public static void zeroToThree(int i) {
        System.out.println(i);
        i++;
        if (i < 4) {
            zeroToThree(i);
        }
 }

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

0
1
2
3

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

So... the first instance of the zeroToThree will print out 0, which is what i is in this particular instance, since 0 is what was inititally sent as a parameter..
The next line of the method has i go up by one, so in this case from 0 to 1. With the next line, 1 is indeed less than 4, 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.)

So with the second instance of zeroToThree starting, its instance of i, which has been passed to it, will be printed - so another line of output; this time 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).

So then the third instance of zeroToThree starts, and prints out what it was sent, which is 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).

The fourth instance of zeroToThree receives 3 as its parameter, so with its first line, 3 is printed out. 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. So this particular instance of zeroToThree by-passes making another call to another instance of zeroToThree, and instead finishes off and so is garbage collected out of memory.

(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. And since the third call to zeroToThree is finished, the method which called it - the second instance of zeroToThree, can finish. And since the second call to zeroToThree is finished, what called it - the first call to zeroToThree, can also finish. And that's it for zeroToThree(0).

 

A more useful variation of the above method would be one 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 countUp(int i, int j) {
        System.out.println(i);
        i++;
        if (i <= j) {
            countUp(i, j);
        }
    }

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.


for, while, and do while, as well as Recursion All Accomplish Iteration

As seen in previous notes, all three looping control stuctures 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 iteration can do the same thing. For example, the following two code segments accomplish the same output (assumming that in the case of zeroToThree, it is sent the parameter 0:


public static void zeroToThree(int i) {
        System.out.println(i);
        i++;
        if (i < 4) {
            zeroToThree(i);
        }
    }
    
    public static void forLoop(){
        for(int i = 0; i < 4; 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, one could aruge 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. In fact, often times a recursive solution will be much more inefficient than its iterative counterparts - 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.

Never-the-less, recursive soutions, often can look a lot more elegant than "iterative" solutions. So you may end up choosing a recursive version which takes up a lot less lines of code than an iterative solution. But it's the reason that it takes up less lines of code which points to the actual valid reson to choose it: the algorithm you've come up with - actually does work, in real life, in a recursive way.

Any time a bigger problem is broken down into a smaller version of the same problem, and that problem is in turn broken down into a smaller version of it, and so on, that is recursion. And often times with such 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.


Recursive Examples

The two standard algorithms (which we will look at in more detail later on) 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 more efficiently) iteratively, the traversal of the binary tree cannot.

The easiest one to consider - even though it's not necessary to use the recursive version - is arguably the binary search. To do it in a recursive way, you repeat the following steps on smaller and smaller sub-arrays: you look at the middle element, and if is what you are looking for 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 takled the same way.)

public static int recursiveBinarySearch(int[] arr, int low, int high, int key) {
    
    if (first < upto) {
        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;  
}


And here's the (necessary, as there's not an iterative approach) traversal recursive solution:

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;
}

 

Fun Examples of Recursion in Action:

Fractals

Entire screen game: http://entire.spacebar.org/