# Foundations of Computer Science/Abstraction and Recursion

## Abstraction and Recursion

Programming is easy as long as the programs are small. Inevitably our
programs will grow larger and larger as we create them to solve
increasingly complex problem. One technique we use to keep our
algorithms and programs simple is
abstraction, which is an
idea widely used in many fields such as art, math and engineering. In
this chapter we will study how to apply this technique is algorithm
design and programming.

An abstraction removes details to help us focus our attention. For
instance, a car present a set of simple controls as an interface to its
drivers. As long as we know how to use the interface we can drive the
car without knowing how it operates under the hood. The internal working
of a car is unnecessary detail to drivers unless they are race car
drivers who need this type knowledges to drive the car most efficiently.
This interface hasn\'t change much since when the first car was made.
Abstraction also generalizes concepts by extracting common features from
specific examples. This car interface extracts common car features (what
a driver needs to know to drive a car) from all kinds of cars. Once you
learn how to drive one car you have learned how to drive all cars of the
same type. This is a powerful idea. Such abstraction also gives car
makers the freedom to change the internal design of a car without
affecting the users.

### Abstraction in Computing

We have learned that algorithm design is an integral part of problem
solving using computing and a first step in programming. The hardest
part isn\'t programming/coding but the keeping track of details in large
programs. There are two primary ways to keep our programs \"small\":
chunking and layering, which are two metaphors for abstraction. Chunking
breaks down (decompose) functionality into smaller units and let units
interact with each other through a well-defined interface. For instance,
in Snap! you can implement an algorithm as a block, which then can be
used anywhere in your script as long as you can call the block with a
proper sequence of parameters according to the interface. Layering
separates the functional units (blocks) into layers to separate concerns
and simply interactions patterns to make the complexity more manageable.
The following figure illustrates the idea of layering.

!By organizing functional units (blocks) into layers we can simply the
interactions and allow concurrent development of the
layers. into layers we can simply the interactions and allow concurrent development of the layers.")

In the figure each layer relies on the layer below it to function and
provides services to the layer above it. For example, a unit in layer
one is only allowed to call units in layer 2 below it. All interactions
are limited to pairs of layers that are next to each other in a stack of
layers. We could replace a layer completely with a new implementation
without affecting the rest of the stack, which achieves modularity. On
the contrary if any arbitrary interaction is allowed we may end up with
tightly coupled system as shown in the following figure.

!Without any restriction any unit (block) can call any other
unit. can call any other unit.")

### Abstraction Examples

Using abstraction to achieve simplification and generalization is truly
a powerful organizing idea. Recall the thought experiment in chapter
one, in which we built a machine that can potentially solve groups of
equations. The machine was built through abstraction - we construct
larger building blocks using smaller (more elementary) ones and treat
each block as a unit ignoring the internal details.

The Snap! environment allows us to construct programs in a similar
fashion. When a block is defined it becomes a new building block (user
defined). The block can be arbitrarily complex, but to use it we only
need to know the interface - its name and its list of parameters. The
unnecessary details are hidden from the users greatly simplifying the
thinking involved in programming.

Lets look at a concrete example. In order to make a sprite to draw
different equal-lateral shapes we can create a block for drawing each
type of shapes such as triangles, squares, pentagons, and etc. A block
in Snap! is an abstraction that hides details and represents a certain
behavior/intention. The following block draws a square with a specific
size.

!This Snap! block draws a square with a specific
size.
To draw a triangle we can use a similar logic structure.

!This Snap! block draws an equal-lateral
triangle.

The draw triangle block repeat three times to draw each side with a turn
of 120 degrees. Do you know why the sprite has to turn 120 degrees to
form a 60 angel between the two sides? I hope you have noticed that the
same logic structure can be used to create blocks for drawing any
equal-lateral shapes. Instead of creating a block for each shape we can
generalize the task into one block that can draw any shapes. This block
needs an additional piece of information - the number of sides.

!The Snap! block can draw any equal-lateral
shape.

With the number of sides we can determines the internal angle of the
shape, which is all we need to draw the shape. Please checkout this
resource
if you are not sure how to calculate the internal angle using the number
of sides. This block can serve as an abstraction of the tasks of drawing
equal-lateral shapes (polygons). You may have noticed the length of the
sides is hard-coded (typed in as a constant not a parameter). What if we
want to draw shapes of different size? We can further generalize the
function of the block by adding anther parameter and use it to control
the side length.

!This Snap! block draws any equal-lateral polygon of any
size.

Through this example, we have demonstrated defining blocks to abstract
away details of a task and generalizing a solution to solve more
problems.

### Recursion

Recursion is a pattern that
is self-similar - the whole consists of smaller parts that are
structurally similar to the whole. For example, a tree consist of
branches that look like smaller trees. Similarly, a directory tree of a
file system on a computer and an ancestry tree genealogy exhibit a
similar pattern. The following figure shows a recursive tree.

!Tree created using the Logo programming language and relying heavily
on
recursion.

Self-similarity allows us to define concepts that exhibit such a pattern
in a more concise and elegant way. A tree can be either a trunk with no
branches or a trunk with a number of branches, each of which is a tree.
This definition covers all possible tree structures. How would you
describe the following picture?

!`A visual form of recursion known as the Droste effect. The woman in this image holds an object that contains a smaller image of her holding an identical object, which in turn contains a smaller image of herself holding an identical object, and so forth.`

If you were to do it by delving into finer and finer details repeatedly
it never ends. Can you define the picture recursively? Another example
is the definition of the factorial function in math$$1!=1$$ and for all
$n>1 n! = n*(n-1)!$ This recursive definition not only defines factorial
but also describes a way to calculate factorial. For example, 5! can be
calculated from 4!, which is 4 times 3!, which is 3 time 2!, which is 2
times 1!, which is 1 by definition.

If the problem we are solving is self-similar - solving the whole
problem is a matter of solving the parts that are similar to the whole -
the solution we are defining for the whole can be used to solve the
subproblems(recursion). The beauty of a recursive solution is that the
definition of the problem is the solution as shown in the factorial
example. To design a recursive solution we practice wishful thinking -
as we describe the solution to whole problem we wish it is fully defined
and can be used to solve the smaller subproblems. In computer
programming, this is called recursive thinking/programming. To program
recursively, we describe the solution to a problem as a
function/procedure/block, in which we break the bigger problems into
smaller ones and use the function we defining to solve the smaller
problems. If the problem is finite, eventually the smaller problems are
so simple that they are directly solvable. In such cases the recursion
stops. We call those cases base cases. By the time our program reaches
all base cases, we would have solved the whole problem because all the
subproblems are solved including the problem we start with. In any
recursive function, two essential parts must exist: base cases and
recursive cases. The recursive cases part breaks a bigger problem into
smaller ones. The base cases stops the recursion by solving the directly
solvable problems. If both parts exists and are structured properly, the
algorithm (function) can solve problems of any size by asking clones of
itself to solve partial problems. Recursive problem solving is a
powerful idea because it simples our thinking: if you can define a
problem recursively you can solve it recursively. Recursive solutions
are more elegant and easy to verify, but it only lends itself to
problems that can be defined recursively.

Before we study some concrete examples we will introduce the concept of
function, which makes recursive solutions more manageable. A block in
Snap! is considered a function (similar to a math function) if it has
the following properties:

-   a function takes an arbitrary number of inputs (zero or more)
-   a function always returns/reports exactly one result value
-   for the same input a function always reports the same result value
-   the execution of a function has no side effects to the environment

With such restrictions functions in Snap! are blocks that performance a
task in isolation (in its own world) and hand off the result to be
further processed. According to the definition what blocks in the
following list are functions?

!Some blocks in this list are
functions.

### Recursion Examples

Consider the binary search algorithm:

`Find an item (target) in a sorted list`\
` if the list is empty, the target cannot be found`\
` consider the item in the middle, if it matches the target you are done `\
` otherwise, decide which half to search next`

To search one half of the ordered list is just a smaller version/part of
the overall problem so we can apply the same algorithm wishing the
algorithm is fully defined. This process goes on till a list is empty or
the search target is found.

Clearly the base cases are

-   if the list is empty, then the target can be found
-   if target in the middle of a list, then the target is found

The recursive cases are (assume the list is sorted in ascending order)

-   if the item in the middle of a list is smaller than the search
    target, continue searching in the second half of the list
-   otherwise, continue searching in the first half of the list

