Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:

Greetings and salutations,
It was 5:00 AM and I still couldn't fall asleep. I was thinking about closures as ways to help make recursive functions iterative. While I had never tried this before, the concept seemed fairly straight forward. I did what any rational person would do in this situation - I went to the computer.

I thought that the Fibonacci series would be a good place to start, because unless you know one of the formulas, the previous two results are required for the next number in the sequence. Closures can remember things can't they? 

#!/usr/bin/perl -w
use strict;

sub fibonacci {
    my ($low, $high) = (1, 0);
    return sub {
        ($low, $high) = ($high, $low + $high);
        return $high;
    };
}
my $iterator = fibonacci();
print $iterator->(), $/ for 1 .. 20;

[download]
But this doesn't quite do what I thought it would (besides skipping 0, which is really the first number in the sequence). I thought I would be able to do something like $fibonacci->(6) and get 8 back from the closure. Oh, I know, wrap the closure in the sub. Iterate as many times as being requested. This way you can take care of edge cases like 0 too. 
sub fibonacci {
    my $fib = shift;
    return $fib if ! $fib || $fib == 1;
    my ($low, $high) = (1, 0);
    my $iterate = sub {
        ($low, $high) = ($high, $low + $high);
        return $high;
    };
    $iterate->() for 1 .. $fib;
    return $high;
}

print fibonacci(0), $/;

[download]
But that didn't look right. Huh? I don't need that closure after all. 
#!/usr/bin/perl -w
use strict;

sub fibonacci {
    my $fib = shift;
    return $fib if ! $fib || $fib == 1;    
    my ($low, $high) = (1, 0);
    for (1 .. $fib) {
        ($low, $high) = ($high, $low + $high);
    }
    return $high;
}

print fibonacci(20), $/;

[download]
Ok, so maybe the Fibonacci series wasn't a good place to start looking at the power of closures as iterators for the purpose of converting typical recursive functions into iterative ones.

So after my long winded lead in, my question is "What is?". In particular, what are some recursive functions that you have personally made iterative? Did you use closures? Would the use of closures made it easier or just got in the way like it did for me? Can I see the code? Enquiring minds want to know....

Cheers - L~R

Replies are listed 'Best First'.
Re: Recursive to Iterative using Closures (Fun with Fibonacci)
by demerphq (Chancellor) on Sep 12, 2003 at 12:56 UTC

    What is?

    Im afraid I dont grok the relevence of closures as iterators to convert recursive routines to iterative ones. But to answer your question a typical example where converting recursive routines to iterative is requie is to implement Firstkey/Nextkey in a hash that ties to a tree-like structure.

    Simply implementing the classic inorder() function of binary trees iteratively is a good learning example.


    ---
    demerphq

    <Elian> And I do take a kind of perverse pleasure in having an OO assembly language...
[reply]
[d/l]
      demerphq,
      Ok - here is what I "thought" knew and what I was thinking.

      Typical recursion case: When a function requires all elements prior to it to be evaluated before it can be evaluated.

      If I work forwards instead of backwards, I can remember what I need to as I go. In the case of the Fibonacci series, I only need the last 2. I was thinking that closures would be an ideal way to "remember" and just move forward from the beginning to the desired element.

      This indeed worked, but turned out not requiring the closure at all. So I was left wondering.

      Cheers - L~R

[reply]
        Recursion is suitable for problems where you can divide the problem into one or more independent subsets; you can solve the problem for the subsets and use the results to efficient calculate the result for the entire set; and each of the subsets should be significantly smaller than the original set.

        A recursive solution for Fibonacci fails the first requirement, the "sets" are not independent (it also fails the third requirement). Calculating the factorial is also a common example for recursion, but that fails the the third requirement, making that the overhead of calling subs is significant, and it's not compensated by simpler code. Recursion can't really beat: 

            my $p  = 1;
       $p *= $_ for 2 .. $n;

        [download]

        Abigail

[reply]
[d/l]
Re: Recursive to Iterative using Closures (Fun with Fibonacci) (examples)
by tye (Sage) on Sep 12, 2003 at 15:12 UTC
[reply]

Back to Seekers of Perl Wisdom