Recursion (computer science): Difference between revisions

Revision as of 18:54, 13 December 2006

Revision as of 00:45, 14 December 2006

Line 90:

==Tail-recursive functions==

{{main|Tail recursion}}

Tail-recursive functions are functions ending in a recursive call. InterestFor of such functions lies inexample, the factfollowing that[[C the(programming caller'slanguage)|C]] returnfunction positionto needslocate nota bevalue savedin ona the[[linked stacklist]] before making theis tail-recursive call: when this call returns, it will branch directly onbecause the previouslylast savedthing return position. Since the caller's returnit positiondoes is savedcall on the stack, this saves space and time. Implementation of this feature depends on the language and on the compiler.itself:

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 133 ⟶ 131:

return count_odds(head->next); /* tail recursion */

}

The significance of tail recursion is that when making a tail-recursive call, the caller's return position need not be saved on the [[call stack]]; when the recursive call returns, it will branch directly on the previously saved return position. Therefore, on compilers which support tail-recursion optimization, tail recursion saves both space and time.

==See also==