Recursion

Lecture overview -- Keyboard shortcut: 'u'

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

Next page: Recursion versus iteration -- Keyboard shortcut: 'n'

Lecture notes - all slides together

Annotated slide -- Keyboard shortcut: 't'

Alphabetic index

Help page about these notes

Recursion and Higher-order Functions - slide 2 : 35

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

Foldoc: recursion