eliminating tail recursion the main benefit of recursive approach to algorithm design is that it allows us to succinctly take advantage of repetitive structure present in many problems by making our algorithm description exploit the repetitive structure in recursive waywe can often avoid complex case analyses and nested loops this approach can lead to more readable algorithm descriptionswhile still being quite efficient howeverthe usefulness of recursion comes at modest cost in particularthe python interpreter must maintain activation records that keep track of the state of each nested call when computer memory is at premiumit is useful in some cases to be able to derive nonrecursive algorithms from recursive ones in generalwe can use the stack data structurewhich we will introduce in section to convert recursive algorithm into nonrecursive algorithm by managing the nesting of the recursive structure ourselvesrather than relying on the interpreter to do so although this only shifts the memory usage from the interpreter to our stackwe may be able to reduce the memory usage by storing only the minimal information necessary even bettersome forms of recursion can be eliminated without any use of axillary memory notable such form is known as tail recursion recursion is tail recursion if any recursive call that is made from one context is the very last operation in that contextwith the return value of the recursive call (if anyimmediately returned by the enclosing recursion by necessitya tail recursion must be linear recursion (since there is no way to make second recursive call if you must immediately return the result of the firstof the recursive functions demonstrated in this the binary search function of code fragment and the reverse function of code fragment are examples of tail recursion several others of our linear recursions are almost like tail recursionbut not technically so for exampleour factorial function of code fragment is not tail recursion it concludes with the commandreturn factorial( - this is not tail recursion because an additional multiplication is performed after the recursive call is completed for similar reasonsthe linear sum function of code fragment and the good fibonacci function of code fragment fail to be tail recursions any tail recursion can be reimplemented nonrecursively by enclosing the body in loop for repetitionand replacing recursive call with new parameters by reassignment of the existing parameters to those values as tangible exampleour binary search function can be reimplemented as shown in code fragment we initialize variables low and highjust prior to our while loopto represent the full extent of the sequence thenduring each pass of the loopwe either find