an inefficient recursion for computing fibonacci numbers in section we introduced process for generating the fibonacci numberswhich can be defined recursively as followsf fn fn- fn- for ironicallya direct implementation based on this definition results in the function bad fibonacci shown in code fragment which computes the sequence of fibonacci numbers by making two recursive calls in each non-base case def bad fibonacci( ) """return the nth fibonacci number "" if < return else return bad fibonacci( - bad fibonacci( - code fragment computing the nth fibonacci number using binary recursion unfortunatelysuch direct implementation of the fibonacci formula results in terribly inefficient function computing the nth fibonacci number in this way requires an exponential number of calls to the function specificallylet cn denote the number of calls performed in the execution of bad fibonacci(nthenwe have the following values for the cn 'sc if we follow the pattern forwardwe see that the number of calls more than doubles for each two consecutive indices that isc is more than twice is more than twice is more than twice and so on thuscn / which means that bad fibonacci(nmakes number of calls that is exponential in