A tech blog....from a guy named Eddie

Recursion

Hello

Hi there. I'm Eddie. This is my blog, and this is also my first post, so I decided to aim high and post about one of my favorite topics. Enjoy


Recursion!

Recursion! Yea! Love it. For anyone who's having trouble understanding it, I hope this post offers some clarity. Before diving in, there're some guidelines we need to look at. This is a different approach to understanding recursion, but to me, it's always made the most sense.


The Coomes Method

the problem

Try googling the Coomes Method. You won't find it. That's because I just made it up. I call this the Coomes Method in honor of professor Judith Coomes, the greatest teacher I’ve ever had, and an awesome breakdancer.

the rules

The Coomes Method plays on the fact that recursion requires a pattern in order to function properly. Rather than trying to find an algorthm to fit the pattern, we're going to let the pattern create the algorthm for us.

There are only two parts to the Coomes Method - all we have to do is define two levels:
Level 0 - this is your given, the argument passed to your function at every iteration
Level 1 - this is your iterator, the action you perform every time you recurse

the game

And then we apply the rule:

Whenever you have something that resembles Level 0, Apply Level 1

Simple

the reward

That’s it. That's all you need to define your recursive function. Let’s look at some examples of how this works.


Fractals

the problem

Let's start with some visuals to make this easier to understand. Here’s an example utilizing fractals. Let’s start with a simple figure:
This is just a straight line, honestly. Now, let’s do something fun with it, like this:

the rules

So this is pretty simple - we want to change the straight line by adding a spike. Boring so far, but lets take another look at that last sentence:
What are we changing? - the straight line
What are we doing to it? - adding a spike

And just like that, we have the conditions we need for the Coomes Method:
Level 0 - when you have a straight line
Level 1 - add a spike

the game

Ok, so, we have these two parts, but now what? Now we have to apply the rule - every time we find something that resembles Level 0, we apply Level 1. If we examine that spike image, we can find 4 things that resemble Level 0:

Each of these 4 straight lines resemble our Level 0 condition, so we apply Level 1 and get something else:

the reward

The point of recursion is that we can continue this process for as long as we like. Here’s what the spike recursion looks like in its first 5 iterations:


Family tree

the problem

Let’s move away from fractals now and look at a real world problem. Imagine you were writing a family tree program and you wanted to find all of your ancestors. So you have a talk with your software and tell it to find all these great people that came before you, but unfortunately, your software is dense and doesn’t understand your request. So you need to be more specific:

You - Ok, start with me and find my parents
Software - I found your parents. Now what?
You - Great. Now find their parents
Software - I found their parents. Now what?
You - Well, keep going. Find their parents too
Software - I found their parents. Now what?
You - ugh....

the rules

Annoying. Your software wants you to spell out every instruction. But there’s an important takeaway from this conversation - a pattern:

Every time your software finds a person, you instruct it to find that person’s parents.

And just like that, we have our recursive rules for the great Coomes Method:
Level 0 - when you have a person
Level 1 - find that person’s parents

the game

Nice, we have the building blocks. But how do we start building? Let's go back to the pattern and extrapolate:

start with me  
  look for my parents  
  when you have them  
    look for their parents  
    when you have them  
      look for their parents  
      when you have them...

Our pseudocode already tells the story. Let’s refactor:

// here is our Level 0  
when you have *some* person  
  // now we have Level 1  
  look for that person’s parents  
  // looks like Level 0 again
  when you have them, then for each parent  
    // we have *some* person again, but instead of repeating Level 1...
    start a new search, but with this parent

Our recursive algorthm is done. Now let’s change our pseudocode to something beautiful. To simplify this process, I'm invoking a fake findParents function:

// when you have *some* person  
var findAncestors = function(person) {  
  var results = [];  
  var parents = [];  
  // look for that person’s parents
  parents = findParents(person);  
  // when you have them, then for each parent  
  for (var i = 0; i < parents.length; i++) {  
    var currentParent = parents[i];  
    // start a new search, but with this parent
    results.push(findAncestors(currentParent));  
  }  
  return results;  
}  

the reward

Now you can kick off the search by running findAncestors(me) and go pour yourself a tasty beverage while your program bounces around your family tree. Go ahead. You deserve it. Call it the intermission before Act III.


Fibonacci Numbers

the problem

And finally, here’s an example of recursion using my favorite, the Fibonacci Numbers. Things will work a little differently here - instead of getting bigger by using recursion to build a large, intricate tree, here, we’re going to get smaller by using recursion to reduce a big problem to a single number. I'll go into more detail later. The rules for Fibonacci are simple - you start with the number 0 and the number 1, and to find the next number, you add the previous two numbers together. The sequence looks like this:
0 1 1 2 3 5 8 13 21 34 55 89 144 ...

the rules

Easy, and if I asked you to count up to the 50’th Fibonacci number, it might take a while, but you could do it. It’s just a matter of adding up a bunch of numbers. But where do you start with your recursive code? If we reevaluate the rules, we see that Coomes saves the day once again:

The rules for Fibonacci are simple - you start with the number 0 and the number 1, and to find the next number, you add the previous two numbers together.

And just like that, we have both parts of our code:
Level 0 - the first two Fibonacci numbers are 0 and 1
Level 1 - to find a number, add together the previous two numbers

the game

And now, when we apply Level 1 every time we see something that resembles Level 0, a pattern shows up:

  • to find Fibonacci 3, add together Fibonacci 1 and Fibonacci 2
  • to find Fibonacci 4, add together Fibonacci 2 and Fibonacci 3
  • to find Fibonacci 5, add together Fibonacci 3 and Fibonacci 4

---> Detour

You may be wondering to yourself how anything here resembles Level 0. Think about the Level 0 rule:

  • The 1st Fibonacci number is 0
  • The 2nd Fibonacci number is 1

Now think about the problem:

  • To find the 3rd Fibonacci number, add together Fibonacci 1 and Fibonacci 2

This resembles Level 0 to me. What do you think? (Incidently, this is the reason I keep italicizing the word "resembles". Sure, Fibonacci 1 doesn't exactly resemble Fibonacci 3, but the number is just a variable, and Fibonacci x definitely resembles Fibonacci x). Anyway, enough of these shenanigans.

<--- /End detour

Whoa, that was weird. You disappeared for a second. So, let’s refactor the pattern we found into some usable pseudocode:

to find Fibonacci of some number x  
  add together Fibonacci x-2 and Fibonacci x-1

Much prettier. Let's go supernova:
Fib(x) = Fib(x-2) + Fib(x-1)

At last, we can write a recursive function that can calculate Fibonacci Numbers for us:

// to find Fibonacci of some number x
var Fibonacci = function(x) {  
  // address Level 0 conditions
  if (x === 0 or x === 1) { return x; }    
  // add together Fibonacci x-2 and Fibonacci x-1
  else { return Fibonacci(x-2) + Fibonacci(x-1); }  

}

the reward

And that's it. You have a functional Fibonacci Number finder. Congrats! Don't spend it all in one place.


Quick note

You may have noticed that the method for calculating Fibonacci is somewhat different from the method of traversing a family tree. As I mentioned earlier, recursion works differently between these two problems. I think this might be a good way to describe it:

  • In a family tree, you start at Level 0 and build a tree up (or out) by finding each ancestor in a series. The same applies to fractals. This is a process that could potentially go on forever.

  • In Fibonacci, you don't start from point zero and calculate up to x. Instead, you start at x and calculate down until you reach a Level 0 condition. Every Fibonacci "branch" has to reach a Level 0 condition eventually, so rather than going on forever, the process will definitely end at some point.

This last point sometimes confuses people. But in the end, it doesn't really matter. As long as you can break down the problem to a recognizable pattern and apply the Coomes Method, you can create a recursive algorthm to solve the problem.