algorithm design techniques the reason that the recursive algorithm is so slow is because of the algorithm used to simulate recursion to compute fn there is one call to fn- and fn- howeversince fn- recursively makes call to fn- and fn- there are actually two separate calls to compute fn- if one traces out the entire algorithmthen we can see that fn- is computed three timesfn- is computed five timesfn- is computed eight timesand so on as figure showsthe growth of redundant calculations is explosive if the compiler' recursion simulation algorithm were able to keep list of all precomputed values and not make recursive call for an already solved subproblemthen this exponential explosion would be avoided this is why the program in figure is so much more efficient asa second examplewe saw in how to solve the recurrence ( ( /nn- = (inwith ( suppose that we want to checknumericallywhether the solution we obtained is correct we could then write the simple program in figure to evaluate the recursion once againthe recursive calls duplicate work in this casethe running time (nsatisfies (nn- = (inbecauseas shown in figure there is one (directrecursive call of each size from to plus (nadditional work (where else have we seen the tree shown in figure ?solving for ( )we find that it grows exponentially figure trace of the recursive calculation of fibonacci numbers double evalint ifn = return else double sum forint ++ sum +evali )return sum nfigure recursive function to evaluate ( /  - = (in