Personal tools

Tail recursion

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Make 'foldl' the object of the link, and move below quote from Brent.)
(formal definition. vague removed.)
Line 5: Line 5:
 
not tail recursive.
 
not tail recursive.
   
With that said, tail recursion is not that useful of a concept in a
+
Here is formal definition of "tail recursive". "<code-haskell>f</code-haskell> occurs in <code-haskell>t</code-haskell>" means <code-haskell>f</code-haskell> is a free variable of <code-haskell>t</code-haskell>.
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 <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.
 
   
Note that [[Fold|foldl]] is always tail recursive.
+
When a function is defined (in <code-haskell>let</code-haskell> or at the top level) as:
  +
f = t
  +
where <code-haskell>f</code-haskell> is a name and <code-haskell>t</code-haskell> is a lambda-term, <code-haskell>f</code-haskell> is ''tail recursive'' iff <code-haskell>f</code-haskell> occurs tail recursively in <code-haskell>t</code-haskell>. <code-haskell>f</code-haskell> ''occurs tail recursively'' in <code-haskell>t</code-haskell> iff <code-haskell>f</code-haskell> occurs in <code-haskell>t</code-haskell> and any of the following holds:
  +
* <code-haskell>t</code-haskell> is variable;
  +
* <code-haskell>t</code-haskell> is "<code-haskell>\var -> t0</code-haskell>" and <code-haskell>f</code-haskell> occurs tail recursively in <code-haskell>t0</code-haskell>;
  +
* <code-haskell>t</code-haskell> is "<code-haskell>t0 t1</code-haskell>" and <code-haskell>f</code-haskell> occurs tail recursively in <code-haskell>t0</code-haskell> and does not occur in <code-haskell>t1</code-haskell>;
  +
* <code-haskell>t</code-haskell> is "<code-haskell>let bs in t0</code-haskell>" and <code-haskell>f</code-haskell> occurs tail recursively in <code-haskell>t0</code-haskell> and for each binder "<code-haskell>var = t1</code-haskell>" in <code-haskell>bs</code-haskell>, <code-haskell>f</code-haskell> does not occur in <code-haskell>t1</code-haskell>;
  +
* <code-haskell>t</code-haskell> is "<code-haskell>case t0 of bs</code-haskell>" and <code-haskell>f</code-haskell> does not occur in <code-haskell>t0</code-haskell> and for each branch <code-haskell>b</code-haskell> in <code-haskell>bs</code-haskell>, <code-haskell>f</code-haskell> does not occur or occurs tail recursively in <code-haskell>b</code-haskell>;
  +
** when we are saying "occur in <code-haskell>b</code-haskell>", <code-haskell>b</code-haskell> has form "<code-haskell>D vars -> t</code-haskell>" (where <code-haskell>D</code-haskell> is some data constructor and <code-haskell>vars</code-haskell> is a sequence of names), we are thinking of the lambda-abstraction "<code-haskell>\vars -> t</code-haskell>" instead of <code-haskell>b</code-haskell>.
  +
  +
Note that [[Fold|foldl]] 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.
   
 
== Source ==
 
== Source ==

Revision as of 00:09, 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 lambda-term, 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" and f occurs tail recursively in t0;
  • t is "t0 t1" and f occurs tail recursively in t0 and does not occur in t1;
  • t is "let bs in t0" and f occurs tail recursively in t0 and for each binder "var = t1" in bs, f does not occur in t1;
  • t is "case t0 of bs" and f does not occur in t0 and for each branch b in bs, f does not occur or occurs tail recursively in b;
    • when we are saying "occur in b", b has form "D vars -> t" (where D is some data constructor and vars is a sequence of names), we are thinking of the lambda-abstraction "\vars -> t" instead of b.

Note that foldl is tail recursive.

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