Recursion via Pascal

Recursion via Pascal by J. S. Rohl is one of a small number of books devoted entirely to recursion in programming. Recursion is a technique where a problem is defined in terms of a simpler version of itself.

The book has over 100 examples and although the code is in Pascal it shouldn't pose too much of a problem for C / Java programmers.

Factorials are the classic example of recursion:

The factorial of a number n (written as n!) is the product of all positive integers below or equal to n.

6! = 6 × 5 × 4 × 3 × 2 × 1 = 720.

n! can be defined recursively as:

0! = 1
n! = n × (n-1)!

Here's the code to calculate factorials in Pascal:

function factorial( n:integer ):integer;
begin
    if n = 0 then
        factorial := 1
    else
        factorial := n * factorial( n-1 )
end

Or in C:

unsigned int factorial( unsigned int n )
{
    if ( n == 0 )
        return 1;
    else
        return n * factorial( n-1 );
}

Or Forth:

: factorial
    dup 0= if
        drop 1
    else
        dup 1- recurse *
    then
;

Rohl first examines some simple examples of recusion: factorials, highest common factor and displaying numbers before moving on to more advanced topics:

• two-level procedures
• recursive data structures
• binary recursion
• recursive sorting algorithms
• mutual recusion

Throughout the book Rohl compares the runtime / complexity to the equivalent iterative code and warns against any potential pitfalls. My favourite example is the code to calculate x^n from “developing the power example, a cautionary tale”:

function p(x:real; n:integer):real;
begin
  if n = 0 then
    p := 1
  else if odd(n) then
    p := p( x, n div 2 ) * p( x, n div 2 ) * x
  else
    p := p( x, n div 2 ) * p( x, n div 2 )
end

Thanks to a small oversight the order of complexity is Ο(n) instead of Ο(log n).

Recursion via Pascal was published in 1984 but remains relevant despite it's age. The text is easy to follow and I'd recommend the book to anyone curious enough to delve further into recursion :-)