2.9 Recursion

Recursion means calling oneself. A recursive program calls itself. When we talk about a recursive program, we actually are talking about a program that has one or more recursive subroutines. A recursive subroutine is one in whose body it calls itself. Recursion is the primary means of flow of control in a functional programming language such as Lisp, or a logical programming language such as Prolog. In the following program, we have a recursive subroutine that converts a sequence of Fahrenheit temperatures to Centigrade. This example is not the best exemplar of a recursive subroutine. It is presented here to illustrate that recursion is an alternative to iteration. Whether recursion is viable as an efficient alternative to iteration in general, depends on how well recursion is implemented in the language and how much emphasis is placed on recursion by the designers of the programming language. Recursion requires significant overhead for implementation. In languages like Lisp and Prolog, recursion is of utmost importance for flow of control and therefore, implemented in a very optimized fashion, and even preferred over iteration. In Perl, recursion is not as well implemented and should be used if the potential number of recursive calls is not excessively large. However, there are problems for which recursion is the best way to think of a solution. The following program has a recursive subroutine.
Program 2.30

#!/usr/bin/perl
#file fahrenheitr.pl

use strict;
my ($lower, $upper, $step);

#print Fahrenheit-Celsius table for 0, 20, ..., 300 degrees Fahrenheit
$lower = 0; #lower limit of temperature table
$upper = 300; #upper limit
$step = 20; #step size
convertR ($lower, $upper, $step);

##############################
#subroutine: recursively go through the Fahrenheit values;
#quit when upper limit crossed
sub convertR{
my ($fahrenheit, $upLimit, $increment) = @_;
my ($celsius);
if ($fahrenheit > $upLimit){return;}
$celsius = 5/9 * ($fahrenheit - 32);
printf "%4.0f %6.1f\n", $fahrenheit, $celsius;
convertR ($fahrenheit + $increment, $upLimit, $increment);
}

The recursive subroutine takes an argument list containing three elements: a Fahrenheit temperature to convert, an upper limit, and an increment. There is one call to this function in the main program.

convertR ($lower, $upper, $step);

The subroutine’s first statement as given below.

my ($fahrenheit, $upLimit, $increment) = @_;

As indicated earlier, a Perl subroutine gets only one argument, a list @_ where the elements are undifferentiated as regards to their identity and purpose. Inside the subroutine, the programmer is advised to give the individual elements of @_ names to make it more readable and maintainable. The three elements in the argument list that the subroutine convertR gets are called $fahrenheit, $upLimit and $increment. These names are declared with my and thus, are available for use only within the block that is the subroutine’s body. A recursive subroutine must have a way to finish or exit. Otherwise, it will recurse for ever eating up all system resources. Like an infinite loop in an iterative statement, an infinite case of recursion must be avoided in writing recursive subroutines by writing one or more judicious termination situations. The subroutine convertR finishes its recursion because of the following statement.

if ($fahrenheit > $upLimit){return;}

If there is a recursive call such that the value of the temperature to convert $fahrenheit is more than the value of $upLimit, the subroutine call ends or returns without doing anything. This ensures that the recursive subroutine does not go on for ever. The subroutine converts the Fahrenheit temperature to Centigrade and prints it. It then recursively calls convertR.

convertR ($fahrenheit + $increment, $upLimit, $increment);

This crucial call to itself makes the subroutine recursive. The second and the third arguments to the recursive call are the same as the original call in the main program. The first argument to the recursive call is the original Fahrenheit temperature incremented by adding $increment. Thus, we have a sequence of recursive calls to convertR.

convertR (0, 300, 20)
convertR (20, 300, 20)
convertR (04, 300, 20)
.
.
.
convertR (300, 300, 20)
convertR (320, 300, 20)

The last call returns or exits because the termination condition is satisfied. The return from the last call causes returns from the previous calls in the backward order. When the first call

convertR (0, 300, 20)

returns the call to

convertR ($lower, $upper, $step);

in the main program finishes. As a result, the whole program’s execution is finished at this time.