# Difference between revisions of "Tail recursion"

(Make 'foldl' the object of the link, and move below quote from Brent.) |
m (Fix inline code formatting. Without deleting paragraphs this time.) |
||

(8 intermediate revisions by 5 users not shown) | |||

Line 5: | Line 5: | ||

not tail recursive. |
not tail recursive. |
||

+ | Here is formal definition of "tail recursive". "<hask>f</hask> occurs in <hask>t</hask>" means <hask>f</hask> is a free variable of <hask>t</hask>. |
||

− | 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 <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. |
||

+ | When a function is defined (in <hask>let</hask> or at the top level) as: |
||

⚫ | |||

+ | f = t |
||

+ | where <hask>f</hask> is a name and <hask>t</hask> is a lambda-term, <hask>f</hask> is ''tail recursive'' iff <hask>f</hask> occurs tail recursively in <hask>t</hask>. <hask>f</hask> ''occurs tail recursively'' in <hask>t</hask> iff <hask>f</hask> occurs in <hask>t</hask> and any of the following holds: |
||

+ | * <hask>t</hask> is variable; |
||

+ | * <hask>t</hask> is "<hask>\var -> t0</hask>" and <hask>f</hask> occurs tail recursively in <hask>t0</hask>; |
||

+ | * <hask>t</hask> is "<hask>t0 t1</hask>" and <hask>f</hask> occurs tail recursively in <hask>t0</hask> and does not occur in <hask>t1</hask>; |
||

+ | * <hask>t</hask> is "<hask>let bs in t0</hask>" and <hask>f</hask> occurs tail recursively in <hask>t0</hask> and for each binder "<hask>var = t1</hask>" in <hask>bs</hask>, <hask>f</hask> does not occur in <hask>t1</hask>; |
||

+ | * <hask>t</hask> is "<hask>case t0 of bs</hask>" and <hask>f</hask> does not occur in <hask>t0</hask> and for each branch <hask>b</hask> in <hask>bs</hask>, <hask>f</hask> does not occur or occurs tail recursively in <hask>b</hask>; |
||

+ | ** when we are saying "occur in <hask>b</hask>", <hask>b</hask> has form "<hask>D vars -> t</hask>" (where <hask>D</hask> is some data constructor and <hask>vars</hask> is a sequence of names), we are thinking of the lambda-abstraction "<hask>\vars -> t</hask>" instead of <hask>b</hask>. |
||

⚫ | |||

⚫ | |||

+ | |||

+ | 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. |
||

+ | |||

+ | == Tail call optimisation == |
||

+ | |||

+ | In many programming languages, calling a function uses stack space, so a function that is tail recursive can build up a large stack of calls to itself, which wastes memory. Since in a tail call, the containing function is about to return, its environment can actually be discarded and the recursive call can be entered without creating a new stack frame. This trick is called ''tail call elimination'' or ''tail call optimisation'' and allows tail-recursive functions to recur indefinitely. |
||

+ | |||

+ | In Haskell, the function call model is a little different, function calls might not use a new stack frame, so making a function tail-recursive typically isn't as big a deal—being ''productive'', via guarded recursion, is more usually a concern. |
||

+ | |||

⚫ | |||

* Brent Yorgey in Haskell-Cafe on [http://www.haskell.org/pipermail/haskell-cafe/2009-March/058607.html Definition of "tail recursive" wrt Folds] |
* Brent Yorgey in Haskell-Cafe on [http://www.haskell.org/pipermail/haskell-cafe/2009-March/058607.html Definition of "tail recursive" wrt Folds] |

## Latest revision as of 14:04, 5 May 2019

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`

.

- 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 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.

## Tail call optimisation

In many programming languages, calling a function uses stack space, so a function that is tail recursive can build up a large stack of calls to itself, which wastes memory. Since in a tail call, the containing function is about to return, its environment can actually be discarded and the recursive call can be entered without creating a new stack frame. This trick is called *tail call elimination* or *tail call optimisation* and allows tail-recursive functions to recur indefinitely.

In Haskell, the function call model is a little different, function calls might not use a new stack frame, so making a function tail-recursive typically isn't as big a deal—being *productive*, via guarded recursion, is more usually a concern.

## See also

- Brent Yorgey in Haskell-Cafe on Definition of "tail recursive" wrt Folds