Recursion

Recursion and iteration are equally expressive. Naive recursion is generally less efficient than naive iteration. However, sophisticated compilers can make recursion efficient, especially for functional programming languages.

Example of recursion optimization - tail recursion! A function is tail recursive if it only returns the output of a recursive call to itself.

Not tail recursive:


final public int factorial(int x) {
    if (x == 1) return 1;
    else return x * factorial(x - 1);
}

Tail recursive version:

final public int fac(int x, int y) {
    if (x == 1) return y;
    else return fac(x - 1, x * y);
}

But! Java doesn’t (or didn’t) optimize this to tail recursion in byte code. It may be done in modern day Java JIT compilers.

Applicative vs Normal Order Evaluation

  • Applicative order - evaluate arguments to subroutines before the call. What we commonly see in languages.
  • Normal order - evaluate args only when (if) needed. Pass representation of unevaluated args to subroutine. Faster code, can avoid runtime error.

Lazy evaluation

Implementation keeps track of which expressions have already been evaluated, and reuses values

Nondeterminacy

Dijkstra advocated use of nondeterminacy for selection and logically controlled loops. Introduced the guarded command notation.

Conditions are “guards”, and their statements are the “guarded commands”. If multiple guards are true during execution, a nondeterministic choice is made.

Concurrency

Nondeterministic constructs are most important in concurrent programming. May have multiple events that can execute at the same time, so a nondeterministic choice must be made by the language. For e.g., Go has a select statement that chooses which of a set of possible send or receive operations will proceed. If one or more can proceed, a single one is chosen via a uniform pseudo-random selection.

Nondeterminacy and fairness

No deterministic algorithm will be satisfactory in the implementation of a nondeterministic construct.

  • Weak fairness - guarantee that no guard that is always true is skipped forever
  • Strong fairness - guarantee that a guard which is infinitely often true is infinitely often chosen
    • need random choice among guards

Some consider pseudo-random number generators are too expensive to use, so many implmentations not provably fair. Many employ circular list (weak fairness). Others use “more random” techniques like reading a fast system clock and computing remainder module number of guards.