Content deleted Content added
Blaisorblade (talk | contribs) →Implementation methods: Scheme requires to optimize any tail calls, not just tail recursion |
Blaisorblade (talk | contribs) →Description: Add references about mandatory tail call optimization in Scheme |
||
Line 6:
For normal, non-recursive function calls, this is usually a [[micro-optimization]] that saves little time and space, since there are not that many different functions available to call. When dealing with recursive or mutually recursive functions, however, the stack space and the number of returns saved can grow to be huge, since a function can call itself, directly or indirectly, a huge number of times. In fact, it often asymptotically reduces stack space requirements from linear, or [[Big-O notation|O]](n), to constant, or [[Big-O notation|O]](1).
If several functions are ''mutually recursive'', meaning they each call one another, and each call they make to one another in an execution sequence uses a tail call, then tail call optimization will give a ''properly tail recursive'' implementation that does not consume stack space. Proper tail recursion optimization is required by the standard definitions of some programming languages, such as [[Scheme (programming language)|Scheme]]<ref>http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-8.html#node_sec_5.11</ref><ref>http://www.r6rs.org/final/html/r6rs-rationale/r6rs-rationale-Z-H-7.html#node_sec_5.3</ref>.
The notion of tail position in Scheme can be defined as follows:
| |||