Recursion versus iteration

Lecture overview -- Keyboard shortcut: 'u'

Previous page: Recursion -- Keyboard shortcut: 'p'

Next page: Tail Calls -- Keyboard shortcut: 'n'

Lecture notes - all slides and notes together

Lecture 2 - Page 3 : 35

Programming Paradigms
Recursion and Higher-order Functions

Recursion versus iteration

Recursive functions are sufficient - but typically memory inefficient - for programming of an iterative process.

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.

In a tail recursion function the recursive call is a tail call (see next slide)

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