it is common to associate set of local objects with procedurei set of variablesconstantstypesand procedures which are defined locally to this procedure and have no existence or meaning outside this procedure each time such procedure is activated recursivelya new set of localbound variables is created although they have the same names as their corresponding elements in the set local to the previous instance of the proceduretheir values are distinctand any conflict in naming is avoided by the rules of scope of identifiersthe identifiers always refer to the most recently created set of variables the same rule holds for procedure parameterswhich by definition are bound to the procedure like repetitive statementsrecursive procedures introduce the possibility of nonterminating computationsand thereby also the necessity of considering the problem of termination fundamental requirement is evidently that the recursive calls of are subjected to condition bwhich at some time becomes false the scheme for recursive algorithms may therefore be expressed more precisely by either one of the following formsp if then [spend [sif then endfor repetitionsthe basic technique of demonstrating termination consists of defining function ( ( shall be the set of variables)such that ( implies the terminating condition (of the while or repeat clause)and proving that (xdecreases during each repetition step is called the variant of the repetition in the same mannertermination of recursion can be proved by showing that each execution of decreases some ( )and that ( implies ~ particularly evident way to ensure termination is to associate (valueparametersay nwith pand to recursively call with - as parameter value substituting for then guarantees termination this may be expressed by the following program schematap(nif then [sp( - )end (np[sif then ( - endin practical applications it is mandatory to show that the ultimate depth of recursion is not only finitebut that it is actually quite small the reason is that upon each recursive activation of procedure some amount of storage is required to accommodate its variables in addition to these local variablesthe current state of the computation must be recorded in order to be retrievable when the new activation of is terminated and the old one has to be resumed we have already encountered this situation in the development of the procedure quicksort in chap it was discovered that by naively composing the program out of statement that splits the items into two partitions and of two recursive calls sorting the two partitionsthe depth of recursion may in the worst case approach by clever reassessment of the situationit was possible to limit the depth to log(nthe difference between and log(nis sufficient to convert case highly inappropriate for recursion into one in which recursion is perfectly practical when not to use recursion recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms this does not meanhoweverthat such recursive definitions guarantee that recursive algorithm is the best way to solve the problem in factthe explanation of the concept of recursive algorithm by such inappropriate examples has been chief cause of creating widespread apprehension and antipathy toward the use of recursion in programmingand of equating recursion with inefficiency