Tail recursion is a way to use a recursive procedure to generate an iterative process.
- In standard recursion, each procedure call requires a push onto the (program) stack. This is so that the called procedure, when done, can pop the stack and return to the caller. (What gets pushed onto the stack is essentially all the information needed to return to the caller.)
- In FOCS, this was like when Kathy asked Kevin to run a procedure and Kevin needed to remember to return the answer to Kathy, who will then add one to it. Kathy got pushed onto the stack, waiting for Kevin to return his answer so she could add one....
Standard loops (e.g., for, while) don't involve procedure calls, so don't involve stack pushes. Once you go on to the next run through the loop, you can forget the previous run.
Tail recursion is a method by which something that looks like a recursive procedure call can be implemented without stack pushes.
Back to FOCS: Kathy calls Kevin, but in this case (i.e., if the code is tail recursive) Kathy arranges it so that Kevin's answer will be Kathy's answer (e.g., she doesn't need to do anything to fix it, like adding one). Instead of waiting for Kevin to finish, Kathy can just ask Kevin to give me his answer directly when he's done. (Kevin's answer will be what Kathy would have told me, so Kathy doesn't have to stick around to relay the answer back.) This means that Kathy doesn't need to be pushed onto the stack....
Some other explanations:
Fact Index Looks like a cache of an older versison of Wikipedia, maybe