Recursion Question

[i_luv_c++]

Hey Guys, I am writing a Recursive Function which picks the best move for Computer(sort of A.I.) i have done all the base cases however couldn't figure out how to deal with the last part.

Given n stones the player can remove 1, 2 or 3 stones per move. The player to remove the last stone loses. If a guaranteed win is possible, the function sets move to the winning move and returns true. If a win is not possible, the function returns false and sets move to 1 (a delaying tactic).

bool bestMove(int stonesLeft, int & move) {
	if (stonesLeft <= 4 && stonesLeft > 1)  {
		move = stonesLeft - 1;
		return true;
	}
	if (stonesLeft > 5) {
		return false;
		move =1;
	}
	if (stonesLeft == 1) {
		move =1;
		return false;
	}
	bestMove(stonesLeft -1, move);
}

[caut_baia]

i've shorted it a bit for you

bool bestmove  (int stonesleft,int& move)  {
   while (bestmove(stonesleft-1,move))  {
      if (stonesleft <=4 && stonesleft > 1)  {
         move=stonesleft-1;
         return true;
       }
      else {
        move=1;
        return false;
       }
    }
 }

[i_luv_c++]

thanks for the shorted version of the code...However i still cnt figure out..so the basic idea is call the same function three times (numstones,1), (numstones,2), (numstones,3) and use that to predict the result for the n amount of stones. I have the idea just cnt figure out how to code it

[StuXYZ]

There are two issues here (a) code given doesn't do the assignment. (b) you don't understand the recursion.

First let us deal with (a). Code given returns false if stones are greater than 5.
That is not true. Consider the case that there are exactly 6 stones. If I take one stone leaving 5, you can take 1 or 2 or 3 leaving 4:3:2. In those cases I would take
3,2,1 stones and you have to take the last stone. So from 6 there is a guaranteed win. So returning false is wrong.

Now we have actually (partially) discovered the solution in that example. If there
are exactly 5 stones and it is my turn to play I will lose [no guaranteed win], equally the same is true of one stone, but 4,3,2 are all guaranteed wins.

So what is the recursive code and how are you going to write it.

Let us start with a simpler example [this one has branching which makes it more complex].

Say you wish to calculate a factorial, then you might write this:

double factorial(const int N)
{ 
   if (N<=1) return 1.0;
   return N*factorial(N-1);
}

Not how for say factorial(5) you make 5 calls to the function of which 4 are from the function itself.

Now the real question is do you need to use a recursive function to do this problem. The reason to ask is that there are several ways to solve the problem. The optimal is to solve it on paper first, and implement the solution. No recursion, simple formula, has a habit of getting you low marks in a computer science class [although I personally think it should not]. Next you can solve the problem in reverse, work out the list of winning/losing [with best play] numbers up to the current game state, again not recursive [but relatively easy]. Finally you can do the recursive decent method, not I don't see how to do that without branching the solution, and that is complex.

[mrnutty]

Just for giggle, here is my solution :

bool hasWinningMove(const int stonesLeft,int& nextMove){
 const float tolerance = 0.00001f;
 //magic formula muhahahhaaa
 float intPart = 0;
 float frac = modf( (stonesLeft+3.0f)/4.0f , &intPart);

 if(frac <= tolerance|| intPart == 0){ 
     nextMove = 1; return false; 
 }
 else{
    int magicHole = int(ceil(4*intPart - 3));
    nextMove = stonesLeft - magicHole;    
	return true;
 }
}

Runs in constant time. Although no guarantees!!!