Recursion (computer science): Difference between revisions

Revision as of 01:01, 1 December 2006

Revision as of 18:54, 13 December 2006

Line 90:

==Tail-recursive functions==

{{main|Tail recursion}}

Tail-recursive functions are functions ending in a recursive call. ForInterest example,of such functions lies in the followingfact [[Cthat (programmingthe language)|C]]caller's functionreturn toposition locateneeds anot valuebe insaved aon [[linkedthe list]]stack isbefore making the tail-recursive call: when this call returns, becauseit will branch directly on the lastpreviously thingsaved itreturn position. Since the caller's return doesposition is callsaved itself:on the stack, this saves space and time. Implementation of this feature depends on the language and on the compiler.

For example, the following [[C (programming language)|C]] function to locate a value in a [[linked list]] is tail-recursive, because the last thing it does is call itself:

<!-- If someone can rewrite these C functions in Pascal or Common Lisp, please go ahead. -->

Line 108 ⟶ 110:

On the other hand, the <code>Factorial</code> function used as an example in the previous section is ''not'' tail-recursive, because after it receives the result of the recursive call, it must multiply that result by <code>x</code> before returning to its caller. That kind of function is sometimes called ''augmenting recursive''.

The <code>Factorial</code> function can be turned into a tail-recursive function:

'''function''' Factorial(acc: integer, x: integer): integer;

'''begin'''

'''if''' x <= 1 '''then'''

Factorial := acc

'''else'''

Factorial := Factorial(x * acc, x - 1);

'''end'''

Function should then be called by <code>Factorial(1, x)</code>.

Notice that a single function may be both tail-recursive and augmenting recursive, such as this function to count the odd integers in a linked list: