Tail recursion
From HaskellWiki
(Difference between revisions)
(formal definition. vague removed.) 
m 

Line 19:  Line 19:  
Note that [[Foldfoldl]] is tail recursive.  Note that [[Foldfoldl]] is tail recursive.  
−  The important concept to know in Haskell is [[guarded recursion]], where any recursive calls occur within a data constructor (such as <hask>foldr</hask>, where the recursive call to foldr occurs 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 and the recursive call delayed until needed.  +  The important concept to know in Haskell is [[guarded recursion]] (see [http://en.wikipedia.org/wiki/Tail_recursion#Tail_recursion_modulo_cons tail recursion modulo cons]), where any recursive calls occur within a data constructor (such as <hask>foldr</hask>, where the recursive call to foldr occurs 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 and the recursive call delayed until needed. 
== Source ==  == Source == 
Revision as of 00:18, 16 June 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.
Here is formal definition of "tail recursive". "f
occurs in t
" means f
is a free variable of t
.
When a function is defined (in let
or at the top level) as:
f = t
where f
is a name and t
is a lambdaterm, f
is tail recursive iff f
occurs tail recursively in t
. f
occurs tail recursively in t
iff f
occurs in t
and any of the following holds:

t
is variable; 
t
is "\var > t0
" andf
occurs tail recursively int0
; 
t
is "t0 t1
" andf
occurs tail recursively int0
and does not occur int1
; 
t
is "let bs in t0
" andf
occurs tail recursively int0
and for each binder "var = t1
" inbs
,f
does not occur int1
; 
t
is "case t0 of bs
" andf
does not occur int0
and for each branchb
inbs
,f
does not occur or occurs tail recursively inb
; when we are saying "occur in
b
",b
has form "D vars > t
" (whereD
is some data constructor andvars
is a sequence of names), we are thinking of the lambdaabstraction "\vars > t
" instead ofb
.
 when we are saying "occur in
Note that foldl is tail recursive.
The important concept to know in Haskell is guarded recursion (see tail recursion modulo cons), where any recursive calls occur within a data constructor (such asfoldr
(:)
Source
 Brent Yorgey in HaskellCafe on Definition of "tail recursive" wrt Folds