Re: deductive databases

Oops! "ken quirici" <kquirici_at_yahoo.com> was seen spray-painting on a wall:
> Christopher Browne wrote:
>> And while recursion is an abstraction that can cause confusion to
>> those new to it, the ways of hiding it tends to lead to code that is
>> more opaque than straightforward recursion would have been.
>
> I have seen recursive algorithms that certainly left ME tangled up;
> I can't remember what they were but they were the A->B;C->A;B->C;D->C;
> A->D type of thing. I have a feeling that people sometimes try to do
> everything by the most compact recursion possible and end up with
> monstrously difficult programs (where by 'program' I mean the main
> routine and all subroutines). In the world of commercial programming
> that I inhabit code readability and maintainability and
> understandability count for more than recursive compactness. I
> hesitate actually to call it elegance, which was my first choice,
> because the kind of thing I sketched out above is not really
> elegant, is it?

In mathematics, it is entirely common for proofs to use recursion.

"Proof by induction" is heavily used.

Once someone is familiar with that, the use of recursion becomes just another technique, and the result is both compact and readable.

If the inductive proof that your algorithm works has 4 statements, then a recursive implementation is quite likely to have somewhere around 4 statements.

Adding in a stack will make it WAY more complicated, and hide the similarities between the proof and the implementation, thereby making it enormously more difficult to be confident that you got it right.

> Would it be fair to say that recursion uses the subroutine call
> arguments to replace stack entries? If so, I would prefer the stack
> as a kind of universally available (let's just say for now)
> state-descriptor, rather than carrying the info around in my
> routine-travel-bag. Although if there is a text floating around
> somewhere that goes into more detail about recursion vs. non-recursion,
> I would appreciate knowing about it. Always willing to turn the page.

No, the converse is what is true.

Recursion is the more basic notion.

In many languages, stacks are used in either representation. In ML, it is common to use heap-based allocation in lieu of stacks; were it not for that, I'd be able to call it "virtually universal" for them to be essentially synonymous.

> There of course are arguments about whether recursion is more
> expensive of computer time than non-recursion - I won't weigh in on
> that argument

That falls TOTALLY into the realm of "implementational details."

If your favorite compiler implements one or the other badly, then one will be massively less efficient than the other.

In Scheme, the language design _requires_ handling tail recursive functions efficiently with the result that coding using a "manual stack" is quite likely to be MASSIVELY less efficient than utilizing tail recursion. With tail recursion, the function is known to be "eating" arguments as fast as they are being generated, such that the recursive call can be treated as a GOTO, and there is no need for any stack.

Thus, faking recursion using a stack would consume ENORMOUS amounts of additional resources for the (rather common) case of tail recursion.

In FORTRAN, the opposite is likely to be true.

-- 
output = ("cbbrowne" "_at_" "gmail.com")
http://linuxdatabases.info/info/postgresql.html
Rules of the Evil Overlord #73. "I will not agree to let the heroes go
free if they  win a rigged contest, even though  my advisors assure me
it is impossible for them to win." <http://www.eviloverlord.com/>