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.
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.
courses.cs.cornell.edu - Tail Recursion - Functional Programming in OCaml
A function is tail recursive if it calls itself recursively but does not perform any computation after the recursive call returns, and immediately returns to its caller the value of its recursive call.
But if you’re going to write functions on really long lists, tail recursion becomes important for performance. Recall (from CS 1110) that there is a call stack, which is a stack (the data structure with push and pop operations) with one element for each function call that has been started but has not yet completed. Each element stores things like the value of local variables and what part of the function has not been evaluated yet. When the evaluation of one function body calls another function, a new element is pushed on the call stack and it is popped off when the called function completes.
When a function makes a recursive call to itself and there is nothing more for the caller to do after the callee returns (except return the callee’s result), this situation is called a tail call. Functional languages like OCaml (and even imperative languages like C++) typically include an hugely useful optimization: when a call is a tail call, the caller’s stack-frame is popped before the call—the callee’s stack-frame just replaces the caller’s. This makes sense: the caller was just going to return the callee’s result anyway.
So when you have a choice between using a tail-recursive vs. non-tail-recursive function, you are likely better off using the tail-recursive function on really long lists to achieve space efficiency. For that reason, the List module documents which functions are tail recursive and which are not.
But that doesn’t mean that a tail-recursive implementation is strictly better. For example, the tail-recursive function might be harder to read. (Consider sum_plus_acc.) Also, there are cases where implementing a tail-recursive function entails having to do a pre- or post-processing pass to reverse the list. On small to medium sized lists, the overhead of reversing the list (both in time and in allocating memory for the reversed list) can make the tail-recursive version less time efficient.
let rec rev_append l1 l2 =
match l1 with
[] -> l2
| a :: l -> rev_append l (a :: l2)
let rev l = rev_append l []A popular example of tail recursion seems to be a function to calculate factorial.
def fact(n: int) -> int:
if n == 0:
return 1
return n * fact(n - 1)The multiplication happens after the deeper call returns, so every frame must stay on the stack to finish its pending * n operation.
To make it tail recursive, the function can be formed as
def fact(n: int, accumulated: 1) -> int:
if n == 1:
return accumulated
return fact(n - 1, accumulated * n)Please check https://github.com/huyfififi/coding-challenges/pull/18 for further discussion (they are in Japanese).
TODO: