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
_{1},..., 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
_{1}... P_{n} - Combine solutions of the subproblems P
_{1}... P_{n}to a solution of the overall problem P