          Lecture 3 - Page 16 : 42
 Functional Programming in SchemeName binding, Recursion, Iteration, and Continuations * Name binding constructs The let name binding expression The equivalent meaning of let Examples with let name binding The let* name binding construct An example with let* The letrec namebinding construct LAML time functions * Conditional expressions Conditional expressions Examples with if Example with cond: leap-year? Example with cond: american-time Example with cond: as-string * Recursion and iteration Recursion List processing Tree processing (1) Tree processing (2) Recursion versus iteration Example of recursion: number-interval Examples of recursion: string-merge Examples with recursion: string-of-char-list? Exercises * Example of recursion: Hilbert Curves Hilbert Curves Building Hilbert Curves of order 1 Building Hilbert Curves of order 2 Building Hilbert Curves of order 3 Building Hilbert Curves of order 4 A program making Hilbert Curves * Continuations Introduction and motivation The catch and throw idea A catch and throw example The intuition behind continuations Being more precise The capturing of continuations Capturing, storing, and applying continuations Use of continuations for escaping purposes Practical example: Length of an improper list Practical example: Searching a binary tree
 Recursion
 Recursive functions are indispensable for the processing of recursive data structures
 Recursion is an algorithmic program solving idea that involves solution of subproblems of the same nature as the overall problem

 Given a problem PIf P is trivial then solve it immediatelyIf P is non-trivial, divide P into subproblems P1 ,..., PnObserve if Pi (i=1..n) are of the same nature as PIf so, use the overall problem solving idea on each of P1 ... PnCombine solutions of the subproblems P1 ... Pn to a solution of the overall problem P The problem solving technique sketched here is called divide and conquer. It is not all divide and conquer problems that involve recursion. But many do in fact. Recursion comes into play when the subproblems P1 ... Pn turn out to be of the same nature as the overall problem, and as such they can be solved by the same 'medicine' as used for the overall problem P.