Re: Grammatical Recursion

From: Florian Laws (fl-usenet-2004_at_void.s.bawue.de)
Date: 12/18/04 

Date: 18 Dec 2004 11:41:21 GMT

On 2004-12-17, Des Small <des.small@bristol.ac.uk> wrote:
>
> 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.

I does, but that only shows that Iteration is in fact just as powerful
as Recursion.

Regards,

Florian

Relevant Pages

  • [SUMMARY] Magic Fingers (#120)
    ... it will stall a loss as long as possible to increase ... hand of one finger and a right hand of two fingers is the same as a left of two ... def do_turn ... we see the code that controls when recursion stops. ...
    (comp.lang.ruby)
  • Re: Software bugs arent inevitable
    ... It relies on the observation that calculation of the fibonacci ... def expo: ... increasing the recursion depth, even though the expo function is ...
    (comp.lang.python)
  • Re: Self function
    ... would guarantee that at least recursion calls the same function ... def global_to_local: ... Make all references to `refname` local instead of global. ...
    (comp.lang.python)
  • Re: general algorithm + ackermann question
    ... I am to write an Ackermann function using recursion which was no ... "A famous recursive function is the Ackermann function which, ... I attempted to rework it with no self-calls, based on some info that I ... If I interpret your terminology correctly, ...
    (comp.programming)
  • Re: list of polynomial functions
    ... claiming that the recursion depth is too great. ... def make_polys: ... return polys ... And yes - I did just sit in on my first functional programming class:) ...
    (comp.lang.python)