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;
     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

November 2020

2223242526 27 28

Recent Entries

Recent Comments

Search My Blog

0 user(s) viewing

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