Fibonacci, an introduction to recursion 2

Recursion can be as simple as:

function foo() {
   //do bar foo();
}
foo();

It is as simple as that, or so you think…

The most common way I have seen that recursion is taught is by learning how to code Fibonacci numbers.

Fibonacci numbers are like so: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, .., where the next number is always equal to the sum of the previous two numbers.
One way to get a certain Fibonacci number is with a loop:

var result = 1,
    term1 = 0,
    term2 = 1,
    i = 1;
while(i < 10)
{
    result = term1 + term2;
    console.log(result);
    term1 = term2;
    term2 = result;
    i++;
}

The above will print the first 10 Fibonacci numbers to the console.
Here is a demo


Another (easier) way to get the first ten Fibonacci numbers is with a recursive function:

function fib(x) {
    if (x === 0) {
        return 0;
    } else if (x === 1) {
        return 1;
    } else {
        return fib(x-1)+fib(x-2);
    }
}

Here is a demo that will print the 10th Fibonacci number to the console

Even the above example might not be the best approach.
The following example calculates the Fibonacci number and caches the previous results so we do not have to keep recalculating them all of the time:

function fibDriver(n) {
  return n === 0 ? 0 : fib(0, 1, n);
}

function fib(a, b, n) {
  return n === 1 ? b : fib(b, a + b, n-1);
}

Demo


Yes, I know what you are thinking –
When will I ever need to use recursion for Fibonacci numbers?
How can I use recursion in a real example?

Here is an example that I have on one of my sites:

I have a table of parents and their descendants and I want to change all of the descendants of one child so this is what I did:

(this is pseudocode, so please do not use this is in the “real” world)

var allDescendants = [];
function getDescendants(row) {
   var rowId = row.id;
   //calls a function that gets all rows with this parent id
   var children = getRowsWithParent(rowId);
   for(var i = 0; i < children.length; ++i) {
      allDescendants.push(children[i]);
      getDescendants(children[i]); //recurse down
   }
}
var tableRow = someRow;
getDescendants(tableRow);
console.log(allDescendants); //now should contain all of the descendant rows

The above is just one example of many of how you can use recursion (and all of its power).

January 10th, 2013 by

2 thoughts on “Fibonacci, an introduction to recursion

  1. Reply move Apr 10, 2013 7:14 am

    I discovered your blog site on google and check a few of your early posts. Continue to keep up the very good operate. I just additional up your RSS feed to my MSN News Reader. Seeking forward to reading more from you later on!

  2. Reply Hoyt Potters Apr 11, 2013 8:16 pm

    This is really interesting, You are a very skilled blogger. I’ve joined your rss feed and look forward to seeking more of your fantastic post. Also, I’ve shared your website in my social networks!

Leave a Reply