Re: Recursive to Iterative using Closures (Fun with Fibonacci)

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...}

Comment on Re: Recursive to Iterative using Closures (Fun with Fibonacci) Download Code

Replies are listed 'Best First'.
Re: Re: Recursive to Iterative using Closures (Fun with Fibonacci) by Limbic~Region (Chancellor) on Sep 12, 2003 at 13:13 UTC
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]
Re: Recursive to Iterative using Closures (Fun with Fibonacci) by Abigail-II (Bishop) on Sep 12, 2003 at 14:33 UTC
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]