How does recursion help us? This is a valid question, seeing as how so far it may appear that taking the time to define a function or problem recursively is extra work, and understanding all the branching recursive method calls can be difficult. However, as I vaguely mentioned during the Ackermann exercise, method calls can blossom exponentially and quickly become unwieldy. In cases like these, a direct formula or implementation can often be more successful and efficient; however, one is not always possible. Often times recursion’s power to help us lies in the ability to define a complex problem in terms we can (hopefully) understand. We will now delve into a common application in which we can see this is true.

     In mathematics, Fibonacci numbers are linked like a backbone to a surprisingly large amount of different concepts. Fibonacci numbers can be defined by a direct formula, but it uses an irrational constant PHI, and a large, complex formula. However, algorithms written to calculate Fibonacci numbers recursively can be quite eloquent and easy to understand.

     If we define fib(0)=1 and fib(1)=1, then fib(n)=fib(n-1)+fib(n-2) (n must be greater than or equal to 2). Therefore, we can define a recursive algorithm as follows:

     We can see in this case, the general case of fib(n) should terminate, as it should always approach fib(0) and fib(1). Wow, as we can see, that is quite easy, and obviously we can see that the algorithm should work. Fibonacci numbers have been related to hundreds of different mathematical (and botanical) concepts from diagonals on Pascal’s triangle to the golden ratios and the golden number. Fibonacci numbers can even be seen in nature as the angle between leaves on plants. For more applications of Fibonacci numbers, check out http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html.

Or, in the mean time, experiment with this applet concerning fibonacci numbers.

     To help you understand exactly how recursive algorithms are helpful and easy we'll look at another real-world application of recursion: sorting. In the field of computer science, sorting algorithms are common. There is a constant search to make better sorting algorithms to speed up the programs that use them. It just so happens that a great number of programs use some sort of sorting or searching algorithm in them, and recursion can make these much more efficient and fast. As computer science enthusiasts or students, most of you have heard of binary search algorithms or sorting algorithms like merge sort and quick sort. A sorting algorithm that uses recursion can have code that is short and sweet, which can decrease the man-hours required in writing or upkeeping the code of the programs. Also, in the case of binary search (I'll describe the process of this algorithm in a bit), the general or average times required for sorting a list of size n is often much better than the iterative counterparts.

     Binary search is a great recursive searching algorithm that can be used on sorted lists of weighted information. The power of the algorithm lies in how it searches the array. Instead of going to each individual item of the list in order and checking it to see if it is the correct item, the binary search algorithm chops the list in half every time it calls itself again. This method operates much like how someone searches a dictionary for a certain word. First, you take the dictionary (the whole list), and you open it up to the middle. If the word you're looking for isn't on that page, you either repeat your method on the first half or the second half of the dictionary. Which half gets searched depends on if the word is lexographically greater or less than the words on the current page. This corresponds to the binary search algorithm calling itself again on either the upper half or lower half of the list, if the middle item wasn't the one we're looking for. This process repeats until we either find the item (item is in the list), or we've cut the list in half as many times as possible, and didnt' find it where it would have to be (item is not in the list). As you can see, even if the item is not in the list (the worst case scenario), many less comparisons are performed than there are items in the list. While a direct searching algorithm would have looked at every item in the list in the worst case scenario.