Re: Defence of recursive programming
- From: Chris F Clark <cfc@xxxxxxxxxxxxxxxxxxxx>
- Date: 24 Jun 2005 16:52:41 -0400
Joachim Durchholz <jo@xxxxxxxxxxxxx> writes:
> Use a higher-order function.
I think there is no argument that a HOF is more concise than either
iteration or recursion. I also think it is more sophisticated (and
less fundamental) than either iteration than recursion.
> I think the difference between learning iterative and recursive is
> more one of thinking habits:
> With recursion, you ignore the step-by-step nature of computing and
> work in terms of equations. You need to learn and practise stating an
> induction hypothesis, and that's a nontrivial thing.
> With iteration, you start with the step-by-step nature of
> computing. (quote continued below)
With more of my dubious ideas (thanks Jerry!), I still think iteration
(as do this, do that, do more until you have done enough) is more
"fundamental" than recursion. I think step-by-step thinking is more
primitive than equational.
> When practicing, you discover that you have trouble
> "bending the control flow back": variables have to serve a dual
> purpose, depending on whether you're first-time into the loop or in a
> later iteration. (Similar problems can exist when exiting from the
> loop. At that point, writing loops turns really nasty.) If you're
> lucky, somebody introduces you to Dijkstra's notion of loop
> invariants, at which point things become quite manageable again (but
> then stating a loop invariant is still nontrivial: it's equivalent to
> stating the induction hypothesis).
That is in some sense the advantage of recursive (equational)
thinking. You are already thinking (naturally) in terms of induction
hypothesis, in terms of forward progress, in terms of how does one
reduce this problem to a smaller one.
I suspect that recursive thinking may be simpler than forming loop
invariants, but I'm not certain. I do know that when a problem
reaches a certain level of complexity, I quit trying to write a loop
and instead call a routine (which may be a recursive instance of the
routine I'm writing).
At this point, I want to mention a specific paper written by Arch
Robinson (then of Kuch Associates) about recursive tree traversals,
something like "Recursive Tree Traversals Considered Harmful". The
point of his paper is that many programmers of the system he supported
wrote mutually recursive routines the iterated over parse trees to
calculate results. They then wondered why (complained that) as their
inputs grew the performance degraded non-linearly. The problem was
that the users weren't properly accounting for the number of
traversals they were doing and the results were n**3 and worse
algorithms. When the recursion was presented to them as loops, the
non-linear performance was immediately apparent, and the users were
able to resolve their problems.
> I think it's probably best to give students a choice. Show them both
> recursion and loops (with invariants), and let them explore
> both. They'll pick up the concept that's easier on them, then explore
> the analogies with the other one.
No question that every (imperative) student should learn both. I
think every student should also be exposed to HOF's as the ultimate
solution, where you don't care about order, just that something gets
done to all the right parts.
BTW, this discussion is relevant to my own work in parser generation.
I am in the process of adding the "visitor pattern" to my tool. I
have noticed that in the visitor pattern, there is often a step when
the pattern recurses. I had previously realized that this recursion
is not related to the visitor itself, but part of the traversal. That
made me realize that the "pattern" has three parts, I call V, I, and
T. The V is the visitor, that action we take at each node of the tree.
The I is the iterator, which is the order we walk over the tree, such
as pre-order, post-order, in-order, or something special. The T is
the tree itself, or the data structure being walked over. At some
level the three parts are separable--you may want to walk over many
different trees, with many different visitors, but do the wlks all in
pre-order fashion. They are also interconnected, what a pre-order
walk means, has much to do with the shape of the tree itself.
Similarly, the visitor is like pattern-matching, and what is done at
each node of the tree depends on the way the tree is labelled.
In any case, I intend to present the pattern as applying a function
(the visitor) using a HOF (the iterator) to a type (the tree). I was
also thinking of allowing the user to have a for-loop version of the
same. I think it is clear now, I want a recursive representation also.
F(n) = F(n.next) + F(n.next.next)
Thanks,
-Chris
.
- Prev by Date: Re: Functional programming problem
- Next by Date: Re: sml/nj open-gl interface
- Previous by thread: Re: Defence of recursive programming
- Next by thread: Re: Jon's many-language ray tracer
- Index(es):
Relevant Pages
|
