As I mentioned in Passing subroutines as arguments, I'm working through SICP and trying to apply what I'm learning to Perl.

SICP contrasts iterative vs recursive processes and the importance of not confusing this with iterative vs recursive procedures. Whereas the term "recursive procedure" refers merely to the syntactic fact that a procedure definition refers to the procedure itself, when we describe a processes as recursive or iterative, we are talking about how the process evolves, not how it is written.

SICP also says that the distinction between process and procedure can be confusing today because most implementation of common languages (including C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose looping constructs. LISP, of course, does not share this defect and will execute an iterative process in constant space, even if the iterative processes is described by a recursive procedure. Languages with this property are called "tail-recursive."

I've translated the examples in SICP into Perl: a theoretically recursive and iterative way to compute factorials. When Perl executes these subroutines, is there any difference between them? Is Perl tail-recursive? 

#!/usr/bin/perl -w

use strict;

my $result = factorial_recursive(5);
print "factorial_recursive(5) returns $result\n";
$result = factorial_iterative(5);
print "factorial_iterative(5) returns $result\n";

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

sub factorial_iterative() {
  my $n = shift;
  return(fi_helper(1, 1, $n));
}

sub fi_helper() {
  my ($product, $counter, $max_count) = @_;
  if ($counter > $max_count) {
    return($product);
  } else {
    return(fi_helper(($counter * $product), ($counter + 1), $max_count
+));
  }
}

[download]

In reply to Iterative vs Recursive Processes by mvaline

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.