There is an old saying according to which, "to understand recursion, you first need to understand recursion". It is indeed a bit difficult to grasp the first time(s), but it is self-evident once you understand.

The archetypal example of a recursive program is the programming of the factorial function. The factorial of an integer may be defined as the product of that number and all the strictly positive integers smaller than the original number. Thus:

fact(4) = 4 * 3 * 2 * 1 = 24
[download]

Implementing a function calculating the factorial of a number can easily be achieved with an iterative loop. For example, computing the factorial of 10:

$ perl -e '
sub fact { 
     my $c = shift; 
     my $result = 1; 
     $result *= $_ for 1..$c; 
     return $result;}  
print fact (shift);' 10
3628800
[download]

The definition given above of the factorial function is a bit loose. A more precise mathematical definition might be a recursive definition:

fact(1) = 1
fact (n) = n * fact (n-1)
[download]

The idea is that if I need to compute fact(3), I know that it is equal to 3 * fact(2). And fact(2) = 2 * fact(1) = 2 * 1 = 2. So that, finally, fact (3) = 3 * 2 = 6.

Implementing this mathematical definition in Perl is quite straight forward:

$ perl -e '
sub fact { 
     my $c = shift; 
     return 1 if $c == 1; 
     $c * fact($c-1);
} 
print fact (shift);' 10
3628800
[download]

This code is doing exactly what I have described with the mathematical definition: the fact function is called recursively with n-1, n-2, etc., until the argument is 1, at which point all the function call returns are executed to return the final value.

Once you understand the process, this is a fairly efficient way of coding things like trees or chained lists traversing algorithms. For example, traversing a directory tree is usually much easier to code with a recursive algorithm than with an iterative one. But usually a bit less efficient time wise if that matters.