# 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. 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. 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)^n^.
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).

[^1]

```{=html}
<references/>
```

[^1]: Niels Fabian Helge von
    Koch.
    (2014). In Encyclopædia Britannica. Retrieved from
    <http://www.britannica.com/EBchecked/topic/958515/Niels-Fabian-Helge-von-Koch>
