recursion run amok although recursion is very powerful toolit can easily be misused in various ways in this sectionwe examine several problems in which poorly implemented recursion causes drastic inefficiencyand we discuss some strategies for recognizing and avoid such pitfalls we begin by revisiting the element uniqueness problemdefined on page of section we can use the following recursive formulation to determine if all elements of sequence are unique as base casewhen the elements are trivially unique for > the elements are unique if and only if the first elements are uniquethe last items are uniqueand the first and last elements are different (as that is the only pair that was not already checked as subcasea recursive implementation based on this idea is given in code fragment named unique (to differentiate it from unique and unique from def unique (sstartstop) """return true if there are no duplicate elements in slice [start:stop"" if stop start < return true at most one item elif not unique(sstartstop- )return false first part has duplicate elif not unique(sstart+ stop)return false second part has duplicate elsereturn [start! [stop- do first and last differcode fragment recursive unique for testing element uniqueness unfortunatelythis is terribly inefficient use of recursion the nonrecursive part of each call uses ( timeso the overall running time will be proportional to the total number of recursive invocations to analyze the problemwe let denote the number of entries under considerationthat islet nstop start if then the running time of unique is ( )since there are no recursive calls for this case in the general casethe important observation is that single call to unique for problem of size may result in two recursive calls on problems of size those two calls with size could in turn result in four calls (two eachwith range of size and thus eight calls with size and so on thusin the worst casethe total number of function calls is given by the geometric summation - which is equal to by proposition thusthe running time of function unique is ( this is an incredibly inefficient function for solving the element uniqueness problem its inefficiency comes not from the fact that it uses recursion--it comes from the fact that it uses recursion poorlywhich is something we address in exercise -