Recursion versus iteration

Lecture overview -- Keyboard shortcut: 'u'

Previous page: Tree processing (2) -- Keyboard shortcut: 'p'

Next page: Example of recursion: <kbd>number-interval</kbd> -- Keyboard shortcut: 'n'

Lecture notes - all slides and notes together

Lecture 3 - Page 20 : 42

Functional Programming in Scheme
Name binding, Recursion, Iteration, and Continuations

Recursion versus iteration

Recursive functions are - modulo use of memory resources - sufficient for any iterative need

Tail recursive functions in Scheme are memory efficient for programming of any iterative process

Tail recursion is a variant of recursion in which the recursive call takes place without contextual, surrounding calculations in the recursive function.

A tail call is the last 'thing' to be done before the function returns. Therefore there is no need to maintain any activation record of such a call - we can reuse the previous activation record. The image series below will illustrate this.

A recursive formulation of the function fak and the accompanying recursive process

A tail recursive formulation of the function fak and the accompanying iterative process without memory optimization

A tail recursive formulation of the function fak and the accompanying, memory optimized iterative process