Page 2 of 2

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

Posted: 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.

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

Posted: 25 Feb 2017 14:59
bobgillies wrote:
Code: Select all
`// global variablestvar: boardtvar: laneMasktvar: currentLanetvar: queenCounttvar: 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.: firstTry4 Queens new to board0b1000 board queenPutboard nextSpot0b0010 board queenPutboard nextSpot;: secondTry4  Queens new to board0b0100 board queenPut board nextSpot0b0001 board queenPut board nextSpot0b1000 board queenPut board nextSpot0b0010 board queenPutboard nextSpot;firstTrysecondTry`

P.S. Method's put and at were never called by a function in my program. Please disregard/delete them.

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

Posted: 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

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

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

Posted: 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.

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.

Cordially,

Bob

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

Posted: 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