# 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.``````

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