**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 numbern(written asn!) is the product of all positive integers below or equal ton.

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 :-)

C uses == for equality

ReplyDeleteAnonymous: thanks, fixed it :-)

ReplyDeleteThe x^n code is in O(n) because p(x, n div 2) is called twice instead of being memoized. Right? :D

ReplyDeleteHere is a factorial function that illustrates a "pure" recursive form:

ReplyDeletelong factorial(long n)

{ return(n>0?(n*factorial(n-1)):1); }

Pascal is definitely one of my favorite languages. Sadly, its often overlooked...

1997 I was amazed by Delphi and ObjectPascal. Today we have Free Pascal and Lazarus, a very productive environment for everything from Linux to Windows to smartphones. And no cost!

ReplyDelete