I'd like to finish up our discussion of tail recursion by giving a little bit of

perspective on how important it is, and then talk about a more precise definition

of what it actually means to be a tail call.

So, first of all, a lot of times when people learn about tail recursion,

they're in a big hurry to make everything tail-recursive and it's worth pointing

out that there are cases where you really cannot do that.

Now technically speaking, you could make every function call a tail-recursive

call, a tail call. But you can't do it without building

other lists and data structures and things that are going to take up just as

much space as your call stack would. The most obvious examples are functions

that process trees. When you're doing a recursive traversal

over the tree, you need to keep track of what part of the tree you have visited

and you haven't so far and the call stack is a great way to do that.

And you were generally not going to end up with tail-recursive functions that

process trees. You can usually use an auxiliary helper

function to make one of your recursive calls, maybe the one over the left child

tail-recursive. But then you somehow need to keep track

of what you need to do for the right child.

So, you're welcome to try it and I think you'll end up seeing that one of your

recursive calls will not be a tail call. I would also make the more general point

that programmers are often in far too big of a hurry to optimize their code.

a lot of programs we write, it's more important that they be straightforward,

and readable, and easy to verify that they do the right thing.

And oftentimes, a shorter, more natural recursive function is perfectly good and

you can always go back and make a tailrecursive function if it becomes

important. The other thing I want to talk about is,

what exactly is a tail call? So, so far, we have a perfectly good

informal definition. Alright? This intuition that it's a call, where

after you make it, the caller has no more work to do.

In other words, you have some call. like F is going to call X,

and that result is the result for the enclosing function.

Alright? But, that works, that's how I think about it,

but how do you know if that's the immediate result?

It turns out, like many things in programming languages, there is an

elegant recursive definition of what it means for a position in a function body

to be a tail position. And then, a tail call is just any

function call that is in a tail position. So a tail position is, there won't be

anything more to do afterwards. Okay?

So I thought I would show you some of the cases of this definition.

It's kind of a top-down recursive definition about what it means to be in

tail position. Alright?

So first of all, if an expression is not in tail position, then neither will any

of its subexpressions be in tail position.

Once something is not in tail position, there's more work to do afterwards,

so none of the subexpressions are going to be the last thing either, because

there will be even more work to do. On a more positive note, if you have a

function definition, like fun f p = e, the body itself is in tail position.

Okay? So we start with the entire function body

and that is a tail position. Now here's a recursive case.

If you have a conditional, like if e then e2 else e3 or similarly for case

expressions, case e of a bunch of branches.

The test that e1 between the if and the then is not in tail position, because we

have more work to do afterwards. But if the conditional is in tail

position, then, so are e2 and e3. If there's nothing more to do after the

conditional, then there will be nothing more to do after e2 and there'll be

nothing more to do after e3. We'll do one of them and that will be the

last thing we do. Let's do a local let expression.

If you have a let expression that is itself in tail position, then the body e

is in tail position, because that also will be something after which there is no

more work to do. So a call, if, if this e were a function call, that would be a

tail call, but none of the expressions in the bindings would be in tail position,

because we still have to do all the other bindings and the body e.

Alright? And just as a final case, if you have the parts of a function call, those

are not end tail position. We have to evaluate e1, and afterwards,

we still have to evaluate e2. We have to evaluate e2 and afterwards, we

still have to do the call. So even if this call overall is in tail

position and is a tail call, any subexpressions, any extra work we do in

e1 and e2, those are not in tail position.

What this means is, if you ever have a nested function call, like f of g of x,

f might be a tail call but g of x never will be because the caller still has to

do the call to f afterwards. So, as is often the case, we have our

intuition of no more work to do and then we can make that definition more precise

in terms of the recursive structure of our programming language.

And that is really enough to precisely understand this idea of tail position,

tail calls, and tail-recursion.