an efficient recursion for computing fibonacci numbers we were tempted into using the bad recursion formulation because of the way the nth fibonacci numberfn depends on the two previous valuesfn- and fn- but notice that after computing fn- the call to compute fn- requires its own recursive call to compute fn- as it does not have knowledge of the value of fn- that was computed at the earlier level of recursion that is duplicative work worse yetboth of those calls will need to (re)compute the value of fn- as will the computation of fn- this snowballing effect is what leads to the exponential running time of bad recursion we can compute fn much more efficiently using recursion in which each invocation makes only one recursive call to do sowe need to redefine the expectations of the function rather than having the function return single valuewhich is the nth fibonacci numberwe define recursive function that returns pair of consecutive fibonacci numbers (fn fn- )using the convention - although it seems to be greater burden to report two consecutive fibonacci numbers instead of onepassing this extra information from one level of the recursion to the next makes it much easier to continue the process (it allows us to avoid having to recompute the second value that was already known within the recursion an implementation based on this strategy is given in code fragment def good fibonacci( ) """return pair of fibonacci numbersf(nand ( - "" if < return ( , else (abgood fibonacci( - return ( +bacode fragment computing the nth fibonacci number using linear recursion in terms of efficiencythe difference between the bad recursion and the good recursion for this problem is like night and day the bad fibonacci function uses exponential time we claim that the execution of function good fibonacci(ntakes (ntime each recursive call to good fibonacci decreases the argument by thereforea recursion trace includes series of function calls because the nonrecursive work for each call uses constant timethe overall computation executes in (ntime