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.

In reply to Re: Recursively executed function in regex RHS, AKA "wait, why does this work?" by Laurent_R
in thread Recursively executed function in regex RHS, AKA "wait, why does this work?" by Cody Fendant

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.