Recursion – the Pascal years

Pascal may have been the first language that took on recursion in any earnest. That was likely because it caught on as a language used to teach programming. Many Pascal textbooks of the late 1970s and 80s contained quite extensive discussions on recursion, and algorithms for implementing it. These algorithms often centred upon the Factorial, or the simple power function. Here is an example of a Pascal function power() which calculates x^n.

function power(x:real; n:integer): real;
begin
   if x=0.0 then power:=0.0
   else if n=0 then power:=1.0
   else if n<0 then power:=power(x,n+1)/x
   else power:=power(x,n-1)*x
end;

The examples were often accompanied by an explanation of the appropriateness of using recursion in the right circumstances. There was always the caveat that recursion is expensive in terms of storage requirements, not unusual in a time when hardware lacked both speed and memory. By the 1980s with machines becoming more “powerful”, examples often included Towers of Hanoi, Binary search, or more complex calculations.

For example, a Pascal program to solve Legendre polynomials is easy due to the recursive nature of the mathematical function defining it, yet it was not considered efficient. Here is a program to calculate the solution to a Legendre polynomial, Pn(x), using a recursive function, with n=3, and x=5.

program legendreR;

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

begin
   writeln('the value of the polyn is:',p(3,5):0:2);
end.

Here is the corresponding iterative program.

program legendreI;

function p(n: integer; x: real) : real;
var
   prev, this, next : real;
   count : integer;
begin
   if n = 0 then
      p := 1
   else if n = 1 then
      p := x
   else begin
      prev := 1;
      this := x;
      for count := 2 to n do
      begin
         next := ((2*count-1)*x*this-(count-1)*prev)/count;
         prev := this;
         this := next;
      end;
      p := next
   end
end;

begin
   writeln('the value of the polyn is:',p(3,5):0:2);
end.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.