Foundations of Computer Science/Recursion Revisited

Recursion Revisited

Recursive solutions provide another powerful way to solve self-similar problems. The example that we will examine is the binary search solution.

How Binary Search Works?

The process for identifying a target item in a sorted list. You start with the first base case which is to directly solve whether the middle item is equal to the target. If the middle item equals the target then the search is complete and the index is reported. If the list is empty then the search reports -1 or not found. Otherwise, decide if the target is greater or less than the middle item to dictate which half of the list to search.

Next, if the middle item is greater than the target the first half of the list is searched, else, we search the second half of the list. This is the same problem that we originally started with making this a recursive or self-similar problem.

The image below is the binary search code implementation. The base cases and recursive cases are labeled.

Binary search is used to find an item (target) in a sorted list. It consists of bases cases and recursive cases that make up the recursive solution.

Binary Search: Abstraction Simplification

One excellent way to simplify the binary search solution is using abstraction. The image previously shown uses a helper block called "middle between" which is used to find the middle index when given the first and last index of a sorted list (see below).

The helper block used in a binary search to find the middle index between the first and last index given as input.

Another way to simplify the binary search solution is adding another level of abstraction. The helper block below shows the target and list being passed in as input into the "binary search for" block (see below). The actual recursive solution is implemented when the recursive search block detects the first and last index of a sorted list. The "binary search for" block allows users to call the recursive search without the user being required to provide the first and last indices. The user will only see the information and/or blocks necessary to start the binary search. The user will not see the recursive search or behind the scenes of the solution).

The binary search helper block that adds another level of abstraction that searches for the target in a list by calling the recursive search block.

Binary Search: Tracing

We have previously discussed simplifying our interface for the recursive search using "binary search for" which takes the target and a list as inputs (see example below). Then, the "recursive search for" is called and the first base case is immediately solved as our target, 9, is not equal to 5. Since the target 9 is greater than 5 (element at the middle index), we search the second half of the list (index 4 to index 5). The process is repeated and the list is split checking the first element at position and/or index 4. The target is greater than 7 and the recursive search is repeated again searching the second half of the list again. The base case 2 immediately solves that the target 9 is equal to 9 in the list; which located at the middle index 5.

Now, since the target has been found at index 5, the recursive search reports back to the second recursive search which in turn reports back to the first recursive search. Finally, index 5 is reported back to the user at top level of the "binary search for" block.

This image shows how to trace the binary search when the target is equal to 9. Step by step the base case and recursive cases are used for reporting.

In the event the target is not found in a list the binary search reports -1 (see below). The same recursive search calls are made, but on the last call the start index is greater than the last index which indicates the target is not found and the end of the list has occurred.

This image shows how to trace the binary search when the target is not found in the sorted list. The solution reports -1 or not found if the target is not in the list.

Koch Curve

In 1904, Helge von Koch discovered the von Koch snowflake curve, "a continuous curve important in the study of fractal geometry" (3). The Koch curve starts with a single line segment that is 1 unit long. Then, the segment is replaced with four new segments, each one-third the length of the original, also called the generator. The process is repeated forever and creates the Koch curve. The image below shows this process for stages 0 to 2.

This shows the generator (stage 0) and iterations of stage 1 and 2 of the Koch curve.

The length of the Koch curve is infinite. The curve is another interesting implementation of recursion where it is self-similar; the curve copies itself over and over.

Koch Snowflake

Using the same Koch curve generator on all three sides of an equilateral triangle we see repeated iterations eventually start to look like a snowflake (please see Koch Snowflake). The snowflake has infinite perimeter and finite area.

Examining each stage of the Koch Snowflake a pattern is created for the number of segments per side, the length, and the total length of the curve as seen below. The number of segments per sides is increased four times the previous stage. The length of the segment is divided into equal thirds each time giving us the length of each segment. The original stage, an equilateral triangle, is why we take three times the number of segments per side divided by the length of a segment raised to the number of the stage currently being implemented.

The Koch Snowflake pattern can be seen by tracking the different iterations.

Exploration Questions

Studying the Koch Curve and Snowflake patterns are established and show how the same process is repeated to generate each stage. We can use the recursive process to solve abstractions of the same problem.

• What would the total length of the N-th iteration be? Look at the patterns made by the numbers both before and after simplifying.
• What do you expect the Koch Curve to look like? In other words, what would you expect to happen if you repeated this infinitely many times?
• What is the length of the Koch Curve?
• Can you estimate the area at each stage? What is the area of the final snowflake?

Reviewing the previous questions we can start to observe the behavior of the Koch Curve and Koch Snowflake.

1. Based on the patterns established it is clear that the total length of the N-th iteration would be 3*(4/3)ⁿ.
2. As the Koch Curve is infinitely repeated it will start to look more smooth as the lines will appear closer and closer although never touching.
3. The length of the Koch Curve is infinity (after applying the generator infinite number of times).
4. The area of the final snowflake is bounded (finite).