📄 tailrecursn.html
字号:
<!DOCTYPE HTML PUBLIC "-//IETF//DTD W3 HTML 2.0//EN">
<HTML lang="en-US">
<HEAD>
<TITLE>tail recursion</TITLE>
<META name="description"
content="Definition of tail recursion,
possibly with links to more information and implementations.">
<META name="keywords" content="tail recursion">
</HEAD>
<BODY BGCOLOR="#FFFFFF">
<H1>tail recursion</H1>
<P>
(algorithmic technique)
<P>
<strong>Definition:</strong>
A special form of <a href="recursion.html" tppabs="http://hissa.nist.gov/dads/HTML/recursion.html"><em>recursion</em></a> where the last operation of a function is a recursive call. The recursion may be optimized away by executing the call in the current stack frame and returning its result rather than creating a new stack frame.
<P><strong>See also</strong>
<a href="collectrecur.html" tppabs="http://hissa.nist.gov/dads/HTML/collectrecur.html"><em>collective recursion</em></a>, <a href="iteration.html" tppabs="http://hissa.nist.gov/dads/HTML/iteration.html"><em>iteration</em></a>.
<P><em>Note:
The following finds the maximum value in a list. <pre> int max_list(list l, int max_so_far)<br> {<br> if (null == l) {<br> return max_so_far;<br> }<br> <br> if (max_so_far < head(l)) {<br> return max_list(tail(l), head(l));<br> } else {<br> return max_list(tail(l), max_so_far);<br> }<br> } </pre> <P> The return value of the current invocation is just the return value of the recursive call. A compiler could optimize it something like the following so it doesn't allocate new space for l and max_so_far on each invocation or tear down the stack on the returns. <pre> <br> int max_list(list l, int max_so_far)<br> {<br> for (;;) {<br> if (null == l) {<br> return max_so_far;<br> }<br> <br> if (max_so_far < head(l)) {<br> max_so-far = head(l);<br> l = tail(l);<br> } else {<br> max_so_far = max_so_far;<br> l = tail(l);<br> }<br> }<br> } </pre> Now there is no need to allocate new memory for the parameters or get rid of it during the returns, so this will run faster. This code transformation is simple enough to do by hand in this example, but it is much harder for complex <a href="recursive.html" tppabs="http://hissa.nist.gov/dads/HTML/recursive.html"><em>recursive</em></a> data structures, such as <a href="tree.html" tppabs="http://hissa.nist.gov/dads/HTML/tree.html"><em>trees</em></a>. <P> Of course, if a compiler is good enough to find and rewrite tail recursion, it will also collapse the loop test, eliminate the assignment of max_so_far to itself, and hoist the assignment of l after the test giving the following: <pre> <br> int max_list(list l, int max_so_far)<br> {<br> while (null != l) {<br> if (max_so_far < head(l)) {<br> max_so-far = head(l);<br> }<br> l = tail(l);<br> }<br> return max_so_far;<br> } </pre></em>
<P>Author: <a href="terms.html#authorPEB" tppabs="http://hissa.nist.gov/dads/terms.html#authorPEB">PEB</a>
<hr>
Go to the
<A HREF="terms.html" tppabs="http://hissa.nist.gov/dads/terms.html">Algorithms, Data Structures, and Problems</A>
home page.
<hr>
If you have suggestions, corrections, or comments, please get in touch
with
<a href="javascript:if(confirm('http://hissa.nist.gov/~black/black.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://hissa.nist.gov/~black/black.html'" tppabs="http://hissa.nist.gov/~black/black.html">Paul E. Black</a>
(<a href="mailto:paul.black@nist.gov">paul.black@nist.gov</a>).
<p>
Entry modified Thu Dec 30 14:08:35 1999.<BR>
HTML page formatted Thu Dec 30 14:08:50 1999.
<P>
This page's URL is
<A href="tailrecursn.html" tppabs="http://hissa.nist.gov/dads/HTML/tailrecursn.html">http://hissa.nist.gov/dads/HTML/tailrecursn.html</A>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -