Content deleted Content added
Fixed claim that tail recursion is more efficient in time. This is implementation dependent, and is usually only a prefactor better for "reasonable" recursion depths. (Before stack thrashing.) |
|||
Line 53:
return 6
into the more [[Algorithmic efficiency|efficient]] variant,
call factorial (3)
Line 62:
return 6
This reorganization saves space because no state except for the calling function's address needs to be saved, either on the stack or on the heap. This also means that the programmer need not worry about running out of stack or heap space for extremely deep recursions. It is also worth noting, in typical implementations, the tail recursive variant will be substantially faster than the other variant, but only by a constant factor, albeit a large one.
Some programmers working in functional languages will rewrite recursive code to be tail-recursive so they can take advantage of this feature. This often requires addition of an "accumulator" argument (<code>acc</code> in the above example) to the function. In some cases (such as filtering lists) and in some languages, full tail recursion may require a function that was previously purely functional to be written such that it mutates references stored in other variables.{{Fact|date=April 2007}}<!-- an example would be good here -->
| |||