Recursion Tails and Performance

November 28, 2018

If a process builds up a chain of deferred operations is called a recursive process. Carrying out this process requires that the interpreter keep track of the operations to be performed later on. In this kind of processes there's some kind of additional information maintained by the interpreter and not described by the program variables which indicates "where the process is".

An iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how these state variables should be updated as the process moves from state to state. Such process is called a linear iterative process. In the iterative process the program variables provide a complete description of the state of the process at any point. If we stop the process at any point we only need to pass in the variables corresponding to the state in which was paused.

In many languages any kind of recursive procedure generates a process that grows in memory as the process goes deeper, but some languages apply a compiler optimization called tail recursion.