another newbie questions, recursion 
Author Message
 another newbie questions, recursion

Hello again ;-)

I was going through the Sedgewick algorithms book converting
the `c' examples to logo and ran into this question about
recursion that I can not figure. The c source is just below
fallowed by it's output fallowed by the logo code I came up
with and it's output.  

The example is to mark the ticks on a ruler, Divide and
Conqer, recursivly. The problem is that I can not get the
output to match ( I marked the logo output where the
deveation
begins). I think I must not be understanding just when
and/or
how expressions are evaluated in logo.

I hope this is not an enapropriate question, I would
appreciate
any advise.

( If the message text formating is screwed up, please let me
know, I
have been having with that too )

void mark( int x, int h)
{
        printf("mark %d %d\n", x, h );

Quote:
}

void rule( int l, int r, int h)
{
        int m = (l+r)/2;
        printf("rule %d %d %d\n", l, r, h );    
        if( h > 0 )
         {
                mark( m,h );
                rule( l,m,h-1);
                rule( m,r,h-1);
         }

Quote:
}

;;  rule 0 8 3
rule 0 8 3
mark 4 3
rule 0 4 2
mark 2 2
rule 0 2 1
mark 1 1
rule 0 1 0
rule 1 2 0
rule 2 4 1
mark 3 1
rule 2 3 0
rule 3 4 0
rule 4 8 2
mark 6 2
rule 4 6 1
mark 5 1
rule 4 5 0
rule 5 6 0
rule 6 8 1
mark 7 1
rule 6 7 0
rule 7 8 0

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;              
to mark :m :h
        (pr "mark :m :h)
end

to rule :l :r :h
        (pr "rule :l :r :h)
        make "m int (:l + :r) / 2

        if( :h > 0) [
                mark :m :h
                rule :l :m  :h - 1
                rule :m :r  :h - 1
        ]
end
;;  rule 0 8 3
mark 4 3
rule 0 4 2
mark 2 2
rule 0 8 3
mark 4 3
rule 0 4 2
mark 2 2
rule 0 2 1
mark 1 1
rule 0 1 0
rule 0 2 0    <------ this is where it starts to wonder off,
it should be 1 2 0
rule 1 4 1
mark 2 1
rule 1 2 0
rule 1 4 0
rule 2 8 2
mark 5 2
rule 2 5 1
mark 3 1
rule 2 3 0
rule 2 5 0
rule 3 8 1
mark 5 1
rule 3 5 0
rule 4 8 0




Mon, 22 May 2000 03:00:00 GMT  
 another newbie questions, recursion

Quote:

>to rule :l :r :h
>        (pr "rule :l :r :h)
>        make "m int (:l + :r) / 2

>        if( :h > 0) [
>                mark :m :h
>                rule :l :m  :h - 1
>                rule :m :r  :h - 1
>        ]
>end

The problem is that in your Logo program M is a global variable,
whereas in your C program it's local to the RULE procedure.

This means that in the C version, each invocation of RULE remembers
its own value for M, but in the Logo version, the MAKE command changes
the value of a shared variable M.  You start getting in trouble when
an invocation from the instruction

        rule :l :m :h-1

returns, and the caller then tries another call to RULE based on
what it thinks is the same value of M it had originally, but is
actually a much smaller M because of the intervening invocations.

To fix it, say

        local "m

before the MAKE.  If you're using Berkeley Logo, you can instead
change the MAKE to LOCALMAKE which will do both at once.

[posted and mailed]



Mon, 22 May 2000 03:00:00 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. RECURSION RECURSION RECURSION ... AAARRGGHHHH

2. Newbie Question (Was: Newbie Question...)

3. NEWBIE: Recursion and iteration

4. Newbie stuck on recursion

5. Newbie emergency - Attempt at recursion broguth CMUCL to a halt

6. Tail recursion and complete recursion?

7. Not a newbie, but a newbie question...

8. Trivial Newbie Question (Newbie)

9. Question about recursion in J

10. Recursion question

11. another question about recursion

12. another question about recursion -- thanks!

 

 
Powered by phpBB® Forum Software