7.5 Recursively Defined Data

While the data you've processed with references up to this point has been rather fixed-structure, sometimes you have to deal with hierarchical data, which is often defined recursively.

For example, a company organization chart has managers with direct reports, some of whom may also be managers themselves, or an HTML table that has rows containing cells—and some of those cells may also contain entire tables. The chart could also show a filesystem consisting of directories containing files and other directories.

You can use references to acquire, store, and process such hierarchical information. Frequently, the routines to manage the data structures end up as recursive subroutines. A recursive subroutine has a branch from which it calls itself to handle a portion of the task, and a branch that doesn't call itself to handle the base cases.

For example, a recursive subroutine handling the factorial function, which is one of the simplest recursive functions, might look like:

sub factorial {
  my $n = shift;
  if ($n <= 1) {
    return 1;
  } else {
    return $n * factorial($n - 1);
  }
}

Here you have a base case where $n is less than or equal to 1, that does not invoke the recursive instance, along with a recursive case for $n greater than 1, which calls the routine to handle a portion of the problem (i.e., compute the factorial of the next lower number).

This task would probably be solved better using iteration rather than recursion, even though the classic definition of factorial is often given as a recursive operation.