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 and notes together  slide -- Keyboard shortcut: 't'  Textbook -- Keyboard shortcut: 'v'  Help page about these notes  Alphabetic index  Course home    Lecture 3 - Page 16 : 42
Functional Programming in Scheme
Name binding, Recursion, Iteration, and Continuations
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 P1 ,..., Pn

    • Observe if Pi (i=1..n) are of the same nature as P

    • If so, use the overall problem solving idea on each of P1 ... Pn

    • Combine 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.