Analyzing the exact complexity of recursive functions can be difficult to do. Finding the Big O of them can be somewhat eyeballed by drawing out charts of how many calls are made for a recursive function to solve a problem. Take the Fibonacci sequence, which has much less repeated work when calculated with iteration but is very elegant to write with recursion (without tail call optimization). (a) Using the description of Fibonacci below to draw out a recursive Fibonacci call for fibonacci(5), the 5th Fibonacci number. The actual calculated values are not as important as the number passed into each Fibonacci call. Just write out the call tree until the termination of the tree down at each F(1) and F(0) leaf. (b) There are many repeated calls going down the recursion tree, especially when calculating the low Fibonacci numbers. If we used record keeping to remember what we calculated previously (of- ten called dynamic programming) then these repeated calculations all the way down the tree would not happen. Keep track of what Fibonacci numbers you’ve calculated and returned back up the tree previously (the tree is evaluated left to right). Cross out the calls that would be eliminated if you used this record keeping approach. (c) Based on the number of function calls, what would you call the complexity of the original recursive Fibonacci? How does the overall complexity of the Fibonacci change if you cut out these repeated calls with the record keeping? Would it make more sense to use iterative Fibonacci or the record keeping recursive Fibonacci? i n t f i b o n a c c i ( i n t n ) { i f ( n < 2 ) r e t u r n n ; r e t u r n. f i b o n a c c i ( n−1) + f i b o n a c c i ( n−2); }
Analyzing the exact complexity of recursive functions can be difficult to
do. Finding the Big O of them can be somewhat eyeballed by drawing
out charts of how many calls are made for a recursive function to solve
a problem. Take the Fibonacci sequence, which has much less repeated
work when calculated with iteration but is very elegant to write with
recursion (without tail call optimization).
(a) Using the description of Fibonacci below to draw out a
recursive Fibonacci call for fibonacci(5), the 5th Fibonacci number.
The actual calculated values are not as important as the number
passed into each Fibonacci call. Just write out the call tree until the
termination of the tree down at each F(1) and F(0) leaf.
(b) There are many repeated calls going down the recursion
tree, especially when calculating the low Fibonacci numbers. If we
used record keeping to remember what we calculated previously (of-
ten called dynamic programming) then these repeated calculations
all the way down the tree would not happen. Keep track of what
Fibonacci numbers you’ve calculated and returned back up the tree
previously (the tree is evaluated left to right). Cross out the calls
that would be eliminated if you used this record keeping approach.
(c) Based on the number of function calls, what would you
call the complexity of the original recursive Fibonacci? How does
the overall complexity of the Fibonacci change if you cut out these
repeated calls with the record keeping? Would it make more sense
to use iterative Fibonacci or the record keeping recursive Fibonacci?
i n t f i b o n a c c i ( i n t n )
{
i f ( n < 2 ) r e t u r n n ;
r e t u r n. f i b o n a c c i ( n−1) + f i b o n a c c i ( n−2);
}
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 2 images
