Ref #1: What’s Recursion

It was recently brought to my attention, thanks to the much appreciated input of a commenter that not everyone reading this blog knows what a fractal is.  As I began to think about how to explain the concept, I started to realize that there may be many such topic that I frequent in my writings that readers are unfamiliar with.  Although I try to give enough background information within each post, perhaps that is not always entirely sufficient.  Therefore, I have decided to create a series of “reference posts” explaining various such things for the sake of increasing the overall accessibility of this site.

Recursion: see recursion.

On its basic level, a recursive algorithm is an algorithm that is somehow defined relative to the same system it is creating.  For example, one might define a geometric sequence recursively as follows:

A1 = 2

An = A(n-1) * 2

This definition would produce the following sequence:

2, 4, 8, 16, 32, 64 … 2^n

In this sequence, I have defined each term relative to the term before it with the exception of the first term which I have given a set starting point.  Since each term is found by doubling the previous term, the overall sequence can be said to be recursive because each part of the sequence is defined relative to another part of the same sequence, and so, more generally, the sequence is defined relative to itself.

Recursion is, however, a broader concept than this and can extend beyond the world of simple algebra.  In fact, recursion can be found all over nature.  A simple example is when two mirrors are held so that they reflect each other.  One ends up with the image of a mirror inside a mirror inside … This is because the image on the mirror is defined relative to itself.

Another simple example of recursion is proof by induction.  In a proof by induction, one proves that an algebraic expression of n is equivalent to each respective term of a sequence by plugging it in recursively.  I will use the same geometric sequence above as an example:

Prove: if   A1 = 2  &  An = A(n-1) * 2  then  An = 2^n

2, 4, … A(n-1) * 2 = An

Assume: An = 2^n

2, 4, … A(n-1) * 2 = 2^n

∵  (2^n) * 2 = 2^(n + 1)     ! plug-in 2^n for the sequence on the left and apply the algorithm

!of multiplying by two to find the next term.  See if that is equal

!to the definition one the right incremented by one.

(2^n) * (2^1) = 2^(n + 1)

2^(n + 1) =  2^(n + 1)

Q.E.D.

Another example of recursion is the algorithm used by a scientific calculator to parse a formula into a computable expression.  That is, if I enter the expression

3 *2+4*3*2 +2

into a scientific calculator, it solves it recursively.  It might, for example, have an evaluate method that takes the first number and applies to it the solution of the rest of the expression (which it finds using the same evaluate method) using the given operation.  If you are familiar with computer science, the code might look something like this (in summary):

double evaluate(String expression){

if(getFirstOperation(expression) == MULTIPLICATION)

return getFirstNumber(expression) *  evaluate(getRestOfExpression(expression))

+ evaluate(getExpressionAfterFirstPlus(expression));

else if(getFirstOperation(expression) == ADDITION)

return getFirstNumber(expression);

//the code would be written a little differently

//inorder to accommodate for other cases

// this is merely an example that would solve

//the above problem

}

Recursion can also be thought of more generally as any process that references itself.  For example, phycology might be considered recursive because it is using the mind to study itself.  Recursion occurs in levels (see “Levels of Recursion”) or iterations.  Every time a recursive algorithm is completed, the system is said to have undergone one iteration or advanced one level of recursion.

Google has a pretty funny joke about recursion.

Advertisements

Add something to the discussion.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s