Re: [Bug-apl] recursive functions - ackerman

[Frederick H. Pitts]

Fausto,

        In general, both m and n will be nonzero.  In that case
                      (m - 1) ack ( m ack (n - 1))
has to be invoked before other paths through the code can return to the
caller.  As a consequence the above expression has to return the final
result (in general, that is).  So ack needs to return to the caller
immediately after the expression is evaluated, the first time its
invoked or any other time its invoked for that matter.  Keep in mind
that recursion (actually double recursion) is being performed here.  The
first recursive call to ack will be the last recursive call to return
and in general, that call will be in the above expression.

Later,

Fred

On Thu, 2015-04-16 at 00:13 +0200, Fausto Saporito wrote:
> Hi Fred,
> 
> 
> maybe I understood but I expected the control was returned to caller
> when the m=0 condition was met and not before.
> 
> 
> If I look better at the program... i can understand that after all the
> "ack" evaluation the program must exit... but in my case was
> performing the n-increment.
> 
> 
> This could be the reason... even if I'm not still sure about it :-)
> 
> 
> thanks again,
> 
> Fausto
> 
> 
> 
> 
> 2015-04-16 0:01 GMT+02:00 Frederick H. Pitts <address@hidden>:
>         On Wed, 2015-04-15 at 23:24 +0200, Fausto Saporito wrote:
>         Hello Fausto,
>         
>                 Because during the recursion each time
>                       (m - 1) ack ( m ack (n - 1))
>         is evaluated, control (with the intermediate result) must be
>         returned to
>         the caller of ack (which will be ack itself except for the
>         initial call
>         to ack), and not fall through to the statement following the
>         above
>         expression. The latter statement increments n which prevents
>         the
>         recursion from terminating properly.
>         
>                 The above explanation is not particularly eloquent,
>         but I hope you get
>         the gist of what I'm trying to say.
>         
>         Regards,
>         
>         Fred
>         
>         > Hi Fred,
>         >
>         >
>         > thanks a lot.
>         >
>         > Now it works... but (maybe it's a stupid question) why that
>         > change? :-)
>         >
>         >
>         > regards,
>         >
>         > Fausto
>         >
>         >
>         >
>         > 2015-04-15 22:37 GMT+02:00 Frederick H. Pitts
>         > <address@hidden>:
>         >         Fausto,
>         >
>         >                 Try changing the fourth line to
>         >
>         >         z←(m-1) ack (m ack (n-1))⋄ →0
>         >
>         >         Regards,
>         >
>         >         Fred
>         >
>         >         On Wed, 2015-04-15 at 21:03 +0200, Fausto Saporito
>         wrote:
>         >         > Hello all,
>         >         >
>         >         >
>         >         > I'm trying to implement ackerman function, but I
>         got no
>         >         luck ... and I
>         >         > cannot understand why this code doesn't work:
>         >         >
>         >         > z←m ack n
>         >         > →(m=0)/∆1
>         >         > →(n=0)/∆2
>         >         > z←(m-1) ack (m ack (n-1))
>         >         > ∆1: z←n+1 ⋄ →0
>         >         > ∆2: z←(m-1) ack 1
>         >         >
>         >         >
>         >         > is the double recursion permitted in APL2 ?
>         >         >
>         >         >
>         >         > thanks,
>         >         >
>         >         > fausto
>         >         >
>         >         >
>         >
>         >
>         >
>         >
>         >
>         
>         
>         
> 
>