This lesson defines the following concepts:

• tail context
• non-tail context
• tail call
• non-tail call
• proper tail recursion
• iteration

This lesson also states rules of thumb concerning the efficiency of non-tail recursion, tail recursion, and iteration as implemented using the looping constructs of most programming languages.

The asymptotic efficiency of tail recursion depends on how the programming language is implemented. In most implementations of most programming languages, tail recursion is implemented so inefficiently that many programs that could run in constant space generate a stack overflow instead.