for fibn+ fibn fibn- and fib fib directnaive transcription leads to the recursive program procedure fib (ninteger)integervar resintegerbegin if then res : elsif then res : else res :fib( - fib( - endreturn res end fib computation of fibn by call fib(ncauses this function procedure to be activated recursively how oftenwe notice that each call with leads to further callsi the total number of calls grows exponentially (see fig such program is clearly impractical fig the activations of fib( but fortunately the fibonacci numbers can be computed by an iterative scheme that avoids the recomputation of the same values by use of auxiliary variables such that fibi and fibi- : : : while do :xx : yy :zi : end notethe assignments to xyz may be expressed by two assignments only without need for the auxiliary variable zx : yy : thusthe lesson to be drawn is to avoid the use of recursion when there is an obvious solution by iteration thishowevershould not lead to shying away from recursion at any price there are many good applications of recursionas the following paragraphs and will demonstrate the fact that implementations of recursive procedures on essentially non-recursive machines exist proves that for practical purposes every recursive program can be transformed into purely iterative one thishoweverinvolves the explicit handling of recursion stackand these operations will often obscure the essence of program to such an extent that it becomes most difficult to comprehend the lesson is that algorithms which by their nature are recursive rather than iterative should be formulated as recursive procedures in order to appreciate this pointthe reader is referred to the algorithms for quicksort and nonrecursivequicksort in sect for comparison the remaining part of this is devoted to the development of some recursive programs in situations in which recursion is justifiably appropriate also chap makes extensive use of recursion in cases in which the underlying data structures let the choice of recursive solutions appear obvious and natural