Hard problems are hard to solve. Duh!

Easy problems are easy to solve. Obviously!

Hard problems can many times be split into smaller easier parts. Hmmm...

This is the guiding principle of recursion. Recursion is a mathematical concept that is a property of a function. Functions are recursive (aka self-referential) if the definition of the function contains a reference to itself.

An example of a recursive function is:

f(x) = f(x - 1) + f(x - 2)

The function's definition is in terms of itself. By the way if the above function looks familiar, it should, and it has a special name. Read on find out its name.

The concept seems easy enough, but in terms of math the practical applications can be obscured (as is many times the case with math).

Actual application:

Let's drop the number mumbo jumbo and look at how recursion works in the real world. I'll bet that you've used a recursively algorithm before. In fact I guarantee that you have. Pick up a book that's nearest to you. For some that will be farther than other's, but I'll wait. Got it? OK, good. Turn to page 73 quick, GO GO GO! Unless you have extraordinary good luck, you used a recursive method (algorithm) to find the page.

Let me tell you how you found the page.

First, you opened to a random page and saw that you didn't get the right page. If you opened to a page higher than 73 then you flipped to a page in the left hand side of the book. If you found a page less than 73 you flipped to a page in the right hand side of the book. You repeated until you found page 73.

That is a recursive agorithm. Written in English/programming psudocode:

findInBook( pages, pageNum )
{
if ( page is pageNum ) exit;

if (page < pageNum)
findInBook( rightHalf( pages ) , pageNum );
else
findInBook( leftHalf( pages ) , pageNum );
}

Recursion, its a beautiful thing. Recursion allow very complex and difficult problem to be solved using small, simple, repeatable smaller problems. I won't go into the details, but sorting lists of numbers and names often times uses recursion. The famous Quicksort being a prime example.

BTW, the above recursive function along with the initial conditions f(1) = 1 and f(2) = 1 is better known as the Fibbonocci Sequence. A mathematical progression that appears throughout nature.

Later.

SUCH A DELUGE OF NEW POSTS... I SHALL INFECT THEM ALL!!!! (P.S. I LOVE CHRIS PALMER)
» Crustache Mcgoocherson (216.230.10.131) on 2005-08-03 09:15:13

Who are you Crustache???
» thecav on 2005-08-03 09:54:08

It is the true information
Today I read on this theme much. ambien online It agree, a useful piece clomid ovulation Charming question cheap phentermine What words... super, an excellent idea buy tramadol It is remarkable, rather valuable phrase buy kamagra 445c54
» Edgardo (221.238.17.245) on 2010-09-06 10:39:15

Name.

URL.

[to enter your email, use "mailto:[email protected]"]
Subject.

Comment.

Word verification.

Copy the first 4 characters only.

If you are a member, try logging in again or accessing this page here.