Personal tools

Tail recursion

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(link to Fold)
(Make 'foldl' the object of the link, and move below quote from Brent.)
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
Line 13: Line 12:
 
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.
  +
  +
Note that [[Fold|foldl]] is always tail recursive.
   
 
== Source ==
 
== Source ==

Revision as of 09:13, 23 May 2010

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.

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.

Note that foldl is always tail recursive.

Source