Recursion

Play audio slide show -- Keyboard shortcut: 'x'

Lecture overview -- Keyboard shortcut: 'u'

Previous page: Recursion and iteration [Section] -- Keyboard shortcut: 'p'

Next page: List processing -- Keyboard shortcut: 'n'

Lecture notes - all slides together

Annotated slide -- Keyboard shortcut: 't'

Textbook -- Keyboard shortcut: 'v'

Alphabetic index

Help page about these notes

Name binding, Recursion, Iteration, and Continuations - slide 16 : 42

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 P
- If P is trivial then solve it immediately
- If P is non-trivial, divide P into subproblems P₁ ,..., P_n
- Observe if P_i (i=1..n) are of the same nature as P
- If so, use the overall problem solving idea on each of P₁ ... P_n
- Combine solutions of the subproblems P₁ ... P_n to a solution of the overall problem P