Introduction to Recursive Programming

CHAPTER 5

Linear Recursion II: Tail Recursion

You are only as beautiful as your last action.

—Stephen Richards

TAIL recursion, also known as “final” recursion, is a form of linear recursion in the sense that the recursive cases only invoke the method once. However, in tail recursion a recursive call is the last action performed by the method. For example, the function in (1.15) is tail-recursive since it does not manipulate the result of the function call in the recursive case. This implies that it will return a value directly obtained in a base case. In addition, functions may require more parameters in order to store intermediate results that will be used in the base cases for providing the final output. The tail-recursive methods seen ...