Re: Grammatical Recursion

From: Des Small (des.small_at_bristol.ac.uk)
Date: 12/17/04 

Date: 17 Dec 2004 18:26:46 +0000

Jacques Guy <jguy@alphalink.com.au> writes:

> Greg Lee wrote:
>
> > As you say, recursion is not equivalent to iteration, contrary to
> > what Jacques said.
>
>
> Merde! I never wrote that. They are _functionally_ equivalent,
> insofar as anything you do through recursive function calls,
> you can do through simple iteration without function calls,
> e.g.:
>
> factorial = 1
> for i=1 to n do
> factorial = factorial * i
> end for

Not all examples are trivial. The Ackermann function, for example:

def Ack(M, N):
    if (not M):
        return( N + 1 )
    if (not N):
        return( Ack(M-1, 1) )
    return( Ack(M-1, Ack(M, N-1)) )

To rewrite this "iteratively" would surely involve hand-management of
a stack, which might as well be recursion. Unless you're going to get
all continuation-passing or something.

[...]

Des
likes filo better as pastry 

-- 
"[T]he structural trend in linguistics which took root with the
International Congresses of the twenties and early thirties [...] had
close and effective connections with phenomenology in its Husserlian
and Hegelian versions." -- Roman Jakobson

Relevant Pages

  • Re: Grammatical Recursion
    ... Jacques> equivalent, insofar as anything you do through recursive ... you can do through simple iteration ... iteration is insufficient and recursion is needed. ... >> patterns as recursive. ...
    (sci.lang)
  • Short koan-like code snippets (was: coerce for arbitrary types)
    ... (defun bfs6 (test children pending) ... The algorithm seems to be a tail-recursive expression of what ... I don't like using tail recursion to emulate iteration, ...
    (comp.lang.lisp)
  • Re: counting BST nodes using iteration
    ... It uses iteration. ... size_t nodecount(node *root) { ... The problem is how to declare the stack size because we do not know ... converting the above recursion into iteration. ...
    (comp.programming)
  • Re: Simple recursive functions in Lisp
    ... (labels ((rev (lst acc) ... becomes a loop variable. ... to the naive car/cdr recursion). ... Another way to express Graham's algorithm is iteration. ...
    (comp.lang.lisp)
  • Re: Software bugs arent inevitable
    ... I suggested that for a given algorithm implemented ... iteration should always be faster by a small factor. ... > recursive function can run out of stack space while the heap still has ... Which is why, in the part you snipped, I said that recursion (unlike ...
    (comp.lang.python)