Difference between revisions of "Tail recursion"
(initialized from Haskell-Cafe) |
(link to Fold) |
||
| Line 4: | Line 4: | ||
1 to it, or consing another element onto the beginning of it), it is |
1 to it, or consing another element onto the beginning of it), it is |
||
not tail recursive. |
not tail recursive. |
||
| + | Note that <hask>foldl</hask> is always [[Fold|tail recursive]]. |
||
With that said, tail recursion is not that useful of a concept in a |
With that said, tail recursion is not that useful of a concept in a |
||
lazy language like Haskell. The important concept to know in Haskell |
lazy language like Haskell. The important concept to know in Haskell |
||
| − | is |
+ | is [[guarded recursion]], where any recursive calls occur within a data |
| − | constructor (such as foldr, where the recursive call to foldr occurs |
+ | constructor (such as <hask>foldr</hask>, where the recursive call to foldr occurs |
| − | as an argument to (:)). This allows the result of the function to be |
+ | as an argument to <hask>(:)</hask>). This allows the result of the function to be |
consumed lazily, since it can be evaluated up to the data constructor |
consumed lazily, since it can be evaluated up to the data constructor |
||
and the recursive call delayed until needed. |
and the recursive call delayed until needed. |
||
Revision as of 21:37, 25 March 2009
A recursive function is tail recursive if the final result of the
recursive call is the final result of the function itself. If the
result of the recursive call must be further processed (say, by adding
1 to it, or consing another element onto the beginning of it), it is
not tail recursive.
Note that foldl is always tail recursive.
With that said, tail recursion is not that useful of a concept in a
lazy language like Haskell. The important concept to know in Haskell
is guarded recursion, where any recursive calls occur within a data
constructor (such as foldr, where the recursive call to foldr occurs
as an argument to (:)). This allows the result of the function to be
consumed lazily, since it can be evaluated up to the data constructor
and the recursive call delayed until needed.
Source
- Brent Yorgey in Haskell-Cafe on Definition of "tail recursive" wrt Folds