Control Flow

• Sequencing - the order in which statements are executed or expressions are evaluated.
• Selection - alternation - a choice between statements in conditionals.
• Iteration - fragment of code to be executed repeatedly. An iteration of a loop: one execution of the loop body.
• Procedural abstraction - encapsulating a collection of control constructs in a unit.
• Recursion - an expression defined in terms of itself. Self-referential routines.
• Concurrency - two or more fragments of code being executed/ evaluated at the same time.

Recursion

• General: any self-referencing expression.
• In computing: a function that calls itself (for a different set of data), or a function that calls other functions that call it back.
• Outline:

  a recursive function typically starts with a few simple base cases for which the answer is easy to find; they are also called terminating conditions;

  then breaks down the problem into smaller ones that can be solved by recursive calls.

Example

(defun factorial (n)
  (if (< n 2) 1
    (* n (factorial (- n 1)))))
(factorial 5)
-> 5 * (factorial 4)
-> 5 * 4 * (factorial 3)
-> 5*4* 3 * (factorial 2)
-> 5*4*3* 2 * (factorial 1)
-> 5*4*3*2*1 -> 120

Recursion vs Iteration

• Iteration and recursion are equivalently powerful mechanisms.
• It is possible to write any iterative function recursively and any recursive function iteratively.
• Recursion adds overhead to a function call but it can make a function much easier to write.
• Iteration is more natural in imperative languages, while recursion is more natural in declarative languages.