Recursion! (shakes fist). My worst enemy and my best friend. Recursion has been the source of much anguish recently because it took me a long time to wrap my head around the idea of a function calling itself in order to do something. I found myself constantly thinking why is this so useful, whats the point? Well, recursion makes incredibly complex functions, incredibly easy to write. Recursion constantly breaks down bigger problems in to smaller versions of the original problem until it reaches the end of the problem, or the "base case." Then the result of these base cases are returned up the recursive chain back to the original call of the function. Something a friend told me which helped me to write recursive functions, was "just focus on the base cases, once you get those right the rest will sort itself out."
An example that really helped me grasp the concept of recursion was the fibonacci sequence. A fibonacci number is the sum of the previous two fibonacci numbers. Seems like a simple enough formula right? F(n) = F(n - 1) + F(n - 2). But how do we write a program to give us say the 5th fibonacci number we want? With recursion no doubt! This problem was interesting for me because it requires two base cases. By the definition of the fibonacci number we need two previous numbers in order to find the next. Therefor we need to create these base cases, the first fibonacci number (0) and the second (1). Once we have these numbers the rest just falls in to place. Now once we declare these base cases (if the first fibonacci number is requested, return 0, and if the second fibonacci number is requested, return 1) we can solve for any general fibonacci number n. This is where I see the beauty in recursion. So we want to find the 5th fibonacci number right? Well all we need is the 4th and 3rd number. We don't know the 4th yet but from our base cases we know that the 3rd is 1 since the 1st and 2nd add to 1. Now we know the 4th fibonacci number is 2 by adding the 3rd and 2nd fibonacci numbers. And finally we know the 5th fibonacci number is 3! How cool is that? With recursion we could find any fibonacci number we want. Writing recursive functions has been incredibly rewarding, efficient and just fun. Now That I have a grasp of it, it has become one of the most useful tools in my programming knowledge, and I can see how useful it is in the world of programming.
An example that really helped me grasp the concept of recursion was the fibonacci sequence. A fibonacci number is the sum of the previous two fibonacci numbers. Seems like a simple enough formula right? F(n) = F(n - 1) + F(n - 2). But how do we write a program to give us say the 5th fibonacci number we want? With recursion no doubt! This problem was interesting for me because it requires two base cases. By the definition of the fibonacci number we need two previous numbers in order to find the next. Therefor we need to create these base cases, the first fibonacci number (0) and the second (1). Once we have these numbers the rest just falls in to place. Now once we declare these base cases (if the first fibonacci number is requested, return 0, and if the second fibonacci number is requested, return 1) we can solve for any general fibonacci number n. This is where I see the beauty in recursion. So we want to find the 5th fibonacci number right? Well all we need is the 4th and 3rd number. We don't know the 4th yet but from our base cases we know that the 3rd is 1 since the 1st and 2nd add to 1. Now we know the 4th fibonacci number is 2 by adding the 3rd and 2nd fibonacci numbers. And finally we know the 5th fibonacci number is 3! How cool is that? With recursion we could find any fibonacci number we want. Writing recursive functions has been incredibly rewarding, efficient and just fun. Now That I have a grasp of it, it has become one of the most useful tools in my programming knowledge, and I can see how useful it is in the world of programming.
ayyyyyyyy
ReplyDelete