Computational processes

Basic types of processes:

1. Recursive process
   • Chain of deferred operations due to a recurse function definition (recursive procedure).
   • Interpreter needs to keep track of all the deferred operations with corresponding memory costs.
   • Linear recursive process if memory grows linearly.
2. Iterative process
   • Stateful such that the full state is summarized by a fixed number of variables with fixed rules for updating the state and appropriate end-conditions.
   • Program variables provide a full description of the state of the process, and therefore can be interrupted and resumed unlike recursive processes.
   • Linear iterative process if number of steps grows linearly (fixed memory cost).
   • This implementation would not need special constructs like for, while, etc to implement loops, can just be done through recursive function calls - tail recursive
     • not commonly supported (ex: C needs loop constructs).
3. Tree recursions
   • Two or more recursive function calls per step.
   • Sometimes highly inefficient because it can end up doing lots of redundant computation, ex: Fibonacci series creates two branches at every split.
   • Either come up with a smart iterative algorithm or make the compiler automatically create and use a look-up table to avoid redundant computation (Memoization).