## Wednesday, 12 January 2011

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

1. C uses == for equality

2. Anonymous: thanks, fixed it :-)

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

4. Here is a factorial function that illustrates a "pure" recursive form:

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

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

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

My thoughts exactly! It has soooo many pros over the C-based languages -and yet because of Unix, people completely shoved it to a dark corner. My aim is to try to promote the language.

6. 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!

7. . Web programming languages have an assortment of precursors: scripting languages, shell languages, increase languages and regular programming languages. learning programming easy Techpally.com

8. This comment has been removed by the author.

9. Native mobile apps promote better user engagement with longer user sessions; this is probably due to the richer user interface provided although this may be set to change with new developments in HTML5.
app developers london