Subscribe to TFoSSDQ's Blog        RSS Feed
-----

Learning Recursion

Icon Leave Comment
I've started down the path of optimization through recursion. Adjusting to the new way of thinking is taking a bit of work, but the concepts are beginning to register. Recursion is very useful for replacing loops and giving a more compact and optimized feel to your code. Though the definition of recursion is quite simple (calling a method inside itself until one arrives at a base case and return some value to avoid stack overflow), the actual application could greatly vary however. Recursive sequences like the Fibonnaci Sequence can be expressed recursively as the sum of the previous two numbers Fn = fn-1 + fn-2 with f0 = 0 and f1 = 1. Without recursion, one would have to write a method to find the xth number in the fibonacci sequence like this:

public static int fib(int x)
{
     int count = 0;
     int fib1 = 0;
     int fib2 = 1;
     int fibSum;
     while(count < x)
     {
          fibSum = fib1+fib2;
          fib1 = fib2;
          fib2 = fibSum;
          count++;
     }
     return fibSum;
}


Seems like a waste of space to me. I greatly prefer the recursive solution as stated above that Fn = Fn-1 + Fn-2 with F0 = 0 and F1 = 1. With that recursive idea we can write this:

public static int fib(int x)
{
     if(x <= 1) //this is our base case so we don't get stack overflow
     {
          return 1;
     }
     return fib(x-1)+fib(x-1); //remember Fn = Fn-1 + Fn-2
}


This method saves space and time and looks much better.

0 Comments On This Entry

 

Trackbacks for this entry [ Trackback URL ]

There are no Trackbacks for this entry

September 2020

S M T W T F S
  12345
6789101112
13141516171819
202122 23 242526
27282930   

Recent Entries

Recent Comments

Search My Blog

0 user(s) viewing

0 Guests
0 member(s)
0 anonymous member(s)

Categories