I've been following this thread on functional vs imperative programming, and
it has raised some questions in my mind. For example:
>> I just wanted to point out that recursion generally is not a
>> benefit at
>> all.
>The benefit of recursion is economy of expression. In some cases
>a recursive solution is clearer and more maintainable than it's
>iterative equivalent.
>Econonomy of expression, along with portability, is the primary reason we
>use high level programming languages.
It seems to me that if you want to do something to all the leaves of a tree
structure of arbitrary branching and depth that recursion is not only the nice
way to do it; but also that an iterative program for doing the same thing
would effectively have to do the same thing as the recursive program - namely
save the state at the branch points so that it could backtrack. So in that
sense there would be no space or time difference for well interpreted or
compiled recursive and iterative progs. However, the recursive program would
be much easier to read and understand because it would hide the details of
saving the state.
Am I correct in this?
>> It is also no special sign of functional programming
>> languages, you
>> can do recursion in most imperative languages as well.
>Recursion is associated with functional programming in that one
>typically implements iterative constructs with recursion in
>functional programming languages. Many functional programming
>languages allow for iteration without recursion, but recursion
>is the typical way of implementing iterative algorithms in
>functional programming languages.
Functional programming languages have a theoretical advantage in that they can
be proved correct by algortithmic (mechanical) procedures. This is because
each function's output depends only on it's input and not on the value of any
other variables that may have been changed by some other part of the program.
Of course such 'pure' functional languages are impractical since one often
wants to execute something for it's side effects (like 'print'). So all real
languages have some extra-functional commands.
Iteration is inconsistent with pure functional programming since, at least
within the iterative loop, what happens depends on the value of side variables
(e.g. the index). However, as noted, if the recursive call is at the 'tail'
then it can always be replaced by an iterative construct. This will be more
efficient and does not invalidate any proof of correctness.
Brent Meeker
