Recursion

Stop show with sound -- Keyboard shortcut: 'x'

Next slide in show -- Keyboard shortcut: 'n'

2 minutes, 42 seconds

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