![]() All of this is due to the fact the we do not consider the work done by other recursive calls. If we count the recomputations, we can see how we calculate the 4th Fibonacci number twice, the 3rd Fibonacci number three times, and the 2nd Fibonacci five times. Each of the computations highlighted in the diagram will have been computed previously. To clarify our ideas further, we can consider the recursive tree resulting from the trace of the program to calculate the 6th Fibonacci number. If we calculate the 36th Fibonacci number, the values of many Fibonacci numbers are calculated repeatedly, over and over. ![]() Notice that FIB(3) is actually calculated twice! This is a problem. The recursive algorithm calculates the 5th Fibonacci number by recursively calling FIB(4) and FIB(3). If we analyze the computation required for the 6th Fibonacci number in both the iterative and recursive algorithms, the truth becomes evident. However, as we will see later, the performance improvements of the iterative solution are worth it. While this function is not terribly difficult to understand, there is still quite a bit of mental gymnastics required to see how this implements the computation of Fibonacci numbers and even more to prove that it does so correctly. The following pseudocode performs the same calculations for the iterative version. The extremely simple and elegant solution to computing Fibonacci numbers recursively is shown below. ![]() Producing the code for finding Fibonacci numbers is very easy from its definition. To complete the definition, we need to specify the base case, which includes two values for the first two Fibonacci numbers: FIB(0) = 0 and FIB(1) = 1. Fibonacci numbers are a great example of this phenomenon. This typically happens when the recursive solutions to a problem end up solving the same subproblems multiple times. Notice that Fibonacci numbers are defined recursively, so they should be a perfect application of tree recursion! However, there are cases where recursive functions are too inefficient compared to an iterative version to be of practical use. Fibonacci numbers are given by the following recursive formula. Next, we will look at calculating Fibonacci numbers using a tree recursive algorithm.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |