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:

Before we move deeper into how recursion actually does work, and sometimes serves a good purpose, the two teaching notes are key:

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**."

Note that you should never use recursion for the sake of using recursion - just to be fancy. This is 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.

Usually when recursion is used it is used because there is no other (or no other straight-forward) iterative way of solving the problem.

**...Now, Understanding Recursion, Continued from 5.1.2**...

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 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.

**Repetition of certain lines of code is achieved by calling multiple instances of the method**. As the looping continues, each instance of the method will be **interrupted** somewhere in the middle, by a call to another instance of that method. And so on and so on. And then, **eventually, one of the instances will have its continue condition be false** 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 of that method, eventually getting back to the initial call, which also ends.

To appreciate this rather complex series of events, consider the following example of a recursive method:

1. public static voidzeroToThree(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

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).

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) { //When this is false, we will have arrived
//at the base case, and skip to return
countUp(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.

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; that we find out something, or print something, or **do anything** **other than** call another recursive instance. 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 the 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.

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 forLoop(){ for(int i = 0; i < 4; i++){ System.out.println(i); } } public static void zeroToThree(int i) { System.out.println(i); i++; if (i < 4) { zeroToThree(i); } return; }

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.

1. Mirrors Real Life

Never-the-less, recursive solutions, 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, which makes it **easier to read and follow**. But it's the reason that it takes up less lines of code which points to the actual valid reason 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**.

2. No iterative solution is possible

The other important consideration is that 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 Explained

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 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]) { returnrecursiveBinarySearch(arr, low, mid-1, key); } else if (key > sorted[mid]) { returnrecursiveBinarySearch(arr, mid+1, high , key); } else { return mid; } } return -1; }

As you will learn in more detail later on, 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???

Think about it: how can you use a for loop to loop through, or a while loop? It's a branching structure, so 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 to note, as we'll also learn later learn, 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 way to do a binary tree traversal; no an iterative approach works.

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.

THE FOLLOWING IS NOT NECESSARY for IB CS any more, BUT GLANCING AT IT WOULDN'T HURT... at least it wouldn't hurt all that much...

And full code links for the binary search tree, with its recursive traversals:

2222 code Binary Search Tree and Node Class Code 2223 codeSpecificBinary Search Tree Implementation

Explanation of recursive traversals (among more details)

2210 notes Binary Search Trees - Traversing Recursively