If a function can recurse, can a method do so as well?

If you have any questions, remarks, ... if you need help... its here...

Re: If a function can recurse, can a method do so as well?

Postby bobgillies » 25 Feb 2017 00:23

#NextSpot does calculate the next safe column to put the queen at. As of right now, I'm still supplying that calculated position as a binary pattern for #queenPut. I'm still scratching my head on the recursion part. :?
bobgillies
 
Posts: 60
Joined: 24 Jan 2017 06:26

Re: If a function can recurse, can a method do so as well?

Postby bobgillies » 25 Feb 2017 14:59

bobgillies wrote:
Code: Select all
// global variables

tvar: board
tvar: laneMask
tvar: currentLane
tvar: queenCount
tvar: queenRank



//*************************************************************************************************

Object Class new: Queens
    ( numQueens, mutable lane ) 

Queens method: initialize( numQueens -- )
    numQueens := numQueens

//* lanes for downleft diagonal, downright diagonal, and vertical threats. *//
    ArrayBuffer newWith( 3 , 0 ) := lane   
    numQueens 2* to laneMask
         numQueens to queenCount
         0 to queenRank
         1 to currentLane
;

 Queens method: at        \ i -- x    //* I don't know why this works! *//
    @lane at
;

 Queens method: put       \ i x --   //* this too! *//
   @lane put
;

       


// queenPut method - mark the position in the vertical lane bit where
// the queen is placed for that row. Usage:   0b0010 Queens queenPut

 Queens method: queenPut  ( n  -- ) 
//  n = bitpattern. 0b0010 queen in the 3rd column of a 4x4 board.   

    1 @lane at n bitOr 1 swap @lane put
    2 @lane at n bitOr 2 swap @lane put
    3 @lane at n bitOr 3 swap @lane put
    queenRank 1+ to queenRank
    1 @lane at 2* laneMask 2* 1- bitAnd 1 swap @lane put
    2 @lane at 2/  2 swap @lane put 
;   

Queens method: nextSpot \
      queenCount queenRank == if "\nAll the queens solved" . return  then
      1 @lane at  2 @lane at  3 @lane at bitOr bitOr laneMask
      while ( dup )     //* while the bitmask has not shifted down to zero. *//
         [ 2dup bitAnd                 
            ifZero: [ 2/                 //*IF it's safe, place Queen in this spot.   *//
                      "\nQueen is to be put next at col" .  currentLane . break
                    ]                       
              else: [ 2/ ]              //* ELSE the lanes of attack are detected.  *//
                                        //* THEN increment the current spot. *//   
              currentLane 1+ to currentLane       
         ]
    2drop  1 to currentLane                           
;


//********************************************test*******************************************


// This code pattern works for a solved 4x4 board.
// next version needs needs for nextSpot to supply the
// next safe spot as a parameter for queenPut or terminate.


: firstTry
4 Queens new to board
0b1000 board queenPut
board nextSpot
0b0010 board queenPut
board nextSpot
;

: secondTry
4  Queens new to board
0b0100 board queenPut
board nextSpot
0b0001 board queenPut
board nextSpot
0b1000 board queenPut
board nextSpot
0b0010 board queenPut
board nextSpot
;

firstTry
secondTry


P.S. Method's put and at were never called by a function in my program. Please disregard/delete them.
bobgillies
 
Posts: 60
Joined: 24 Jan 2017 06:26

Re: If a function can recurse, can a method do so as well?

Postby Franck » 25 Feb 2017 20:32

bobgillies wrote:Hi Franck, here's a neat side effect I wasn't expecting. It would seem that the THEN clause gets pushed onto the return stack each time SELF is called.

: barfly (self )
self 8 > ifTrue: [ "\n\nI've had me a beer ev'time ah been here!" .
"\n\nAnd ahwul have me another! " . return ]
else: [ "chug " . self 1+ barfly ]
"\nAnd another!" .
;

true barfly

:lol:


Hi,

Sorry, I don't understand the side effect you are talking about.
For me, this works like a recursion should work.
What do you except for this recursion to do ?

return does not stop the computation : it comes back to the caller of the function.

Be carefull also, "self" is not called, self just push the parameter "self" on the stack.
Btw, you should not call your parameters "self" because a function does not have receiver. For readability, I suggest you to use another name (n for instance).

Also, here, the way "return" is used, the "else" clause is not necessary. The #barfly you wrote is the same as this one :

Code: Select all
: barfly ( n )
   n 8 > ifTrue: [
      "\n\nI've had me a beer ev'time ah been here!" .
      "\n\nAnd ahwul have me another! " .
      return
      ]
   "chug " .
   n 1+ barfly
   "\nAnd another!" .
;


Is it what you wanted ?

Franck
Franck
 
Posts: 145
Joined: 29 Oct 2014 19:01

Re: If a function can recurse, can a method do so as well?

Postby bobgillies » 26 Feb 2017 02:32

After some study on what I thought was a neat side effect I should make a confession. Only after reading up on recursion did I realized that I have an almost total lack of understanding regarding recursion. :oops:

I think my code an example of what's called Tail Recursion. Am I right?

Anyway they say that recursive algorithms can be easier to conceptualize. I'm still more comfortable with iteration, and although the text I have on the 8 Queens Problem mentions it can be solved using iteration, the 8 Queens algorithm was provided in pseudo-code using recursion. So recursion it'll be. :)

In my intent on trying to understand recursion for the 8 Queens Problem, I did so in a silly sort of way in what would constitute a "true barfly" for laughs only. :mrgreen:

As always, I learn more every time I log in here.

Cordially,

Bob
bobgillies
 
Posts: 60
Joined: 24 Jan 2017 06:26

Re: If a function can recurse, can a method do so as well?

Postby Franck » 27 Feb 2017 12:08

There is a recursion each time a word call itself into its defintion.

Some algorithms are smaller / cleaner with a recursion.
But the counterpart is that you need more space for the return stack as it will grow for each call (with at least the return address but also the word locals) until the condition that stops the recursion is reached.

For instance, to calculate the factorial of a number ( 1 * 2 * 3 ... * n ), you can write (without recursion) :

Code: Select all
: fact       \ n -- n!
| i |
   1 swap loop: i [ i * ]
;


Or you can use a recursion, as you can write :
fact(0) = 1
fact(n) = fact(n-1) * n ( ie 1*2*3*... *n = n * 1*2*3*...*n-1 = n * fact(n-1) )


So :
Code: Select all
: fact ( n )
   n ifZero: [ 1 ] else: [ n 1- fact n * ]
;


When you call fact(5)
1) n = 5 so it pushes 5 on the stack, substrat 1 and call fact again.
2) n = 4 so it pushes 4 on the stack, substrat 1 and call fact again.
3) n = 3 so it pushes 3 on the stack, substrat 1 and call fact again.
4) n = 2 so it pushes 2 on the stack, substrat 1 and call fact again.
5) n = 1 so it pushes 1 on the stack, substrat 1 and call fact again.
6) n = 0 so it just pushes 1 on the stack and returns.
7) fact(1) pushes 1 (from RS) on the stack and call * ==> 1
8) fact(2) pushes 2 (from RS) on the stack and call * ==> 2
9) fact(3) pushes 3 (from RS) on the stack and call * ==> 6
10) fact(4) pushes 4 (from RS) on the stack and call * ==> 24
11) fact(5) pushes 5 (from RS) on the stack and call * ==> 120.

So you end with 120 on the stack ( ie fact(5) )

Franck
Franck
 
Posts: 145
Joined: 29 Oct 2014 19:01

Previous

Return to General

Who is online

Users browsing this forum: No registered users and 1 guest