understanding recursion

[heraclies]

Can someone give me a comprehensive line by line explanation of how this code works? It's a backtracking algorithm and I know that it does work, but I'm trying to better understand how each line works. let me know if you need a rephrase of the question or if you need more of the code as a reference.

 bool SolveSudoku(int board[][9], bool possible[]
        if (possible[num])
        {
            board[row][col] = num;
            if (SolveSudoku(board, possible, z))
             {
               return true;
             }
            board[row][col] = 0;
        }

[kbw]

You've left some of the code out. There isn't anything to explain.

[doug4]

Line 1 is incomplete--it has 2 arguments and no closing ')' or opening '{', but the recursive call in line 5 has 3 arguments.

In line 2 the value num magically appears. The code checks to see if the value at the num index of the possible array is true. If so, it does the code in lines 4 - 9.

In line 4 the value of the board 2-D array at index [row][col] is set to the value num. Here, row and col also magically appear.

In line 5, you recursively call SolveSudoku passing the (modified) board 2-D array, the possible array, and the mysterious value z. If the code were complete, the program would preserve your current location and values on the call stack and start executing again at line 2. Because board and possible are passed as pointers, changes to the memory to which they point will persist after the function call returns.

When the recursive call returns, the first call to the function takes over again. If the recursive call returned true, this call also returns true. If the recursive call returns false, the value of board[row][col] reverts to 0 (row and col are still not defined), and the code drops into the great abyss below line 10. Obviously black magic happens here because there is no code to tell us what should happen. It's a miracle that it compiles, much less that you "know that it does work."

[heraclies]

The reason I didn't post the entire function was because I am trying to learn more of the conceptual side of recursion and what happens while it runs, since I was having trouble and I got some help with this function but they didn't explain recursion to me that well, especially I would like to know about the whole stacking concept that doug4 was talking about. The whole code for the function is

/**********************************************************************
  * Solver function that will guess between the possible numbers that
  * can go in a square and will keep guessing until it gets the board
  * correct.
  ***********************************************************************/
 bool solveSudoku(int board[][9], bool possible[], int &z)
 {
    int row, col;
    int *testr = &row;
    int *testc = &col;

    //used for finding where the next open space to play is
    if (!FindUnassignedLocation(board, row, col))
    {
       return true;
    }
    //loop for choosing a number to try and will call compute value to see
    //if it is one of the possible numbers to go in the square
    for (int num = 1; num < 10; num++)
    {
       computeValues(possible, board, testr, testc);
       //just a fun little counter to see how many guesses it took
       z++;
       if (possible[num])
       {
          board[row][col] = num;
          if (solveSudoku(board, possible, z))
          {
             return true;
          }
          board[row][col] = 0;
       }
    }
    return false;
 }

Let me know if anything still seems like just magic happening with no explanation.

[kbw]

The details are in the previous post by doug4. But to add to that, the algorithm is run for all possible value (that is, num: [1..9]) in each recursion. State is maintained by placing numbers on the board and clearing them if it doesn't work out (by using zero).

The general idea is:

solution: boolean
   for each number : 0 .. 9
      for each free place on board
      place the number in the free space
      if it's not a solution
         undo it 

Finally, you don't need testr and testc, using row and col directly is clearer.

computeValues(possible, board, &row, &col);

[dhayden]

Also, it looks to me like the call to computeValues() could go above the for loop, which would make it a lot more efficient.

[Flaze07]

why use recursion and not loop instead ??
recursion is slower than loop

[Flaze07]

ah...I almost become one of those stackover flow douchebags...

[jonnin]

Compilers optimize tail recursion to a loop for you when they can. There are a small # of problems that are a little easier to write with recursion, with no penalty. There are a few more that are easier to write, but its a little slower, considered acceptable when performance is not an issue.

I generally avoid it in favor of a loop unless I see a strong reason to do it with recursion. I think I have used it maybe once every 5 years on the average in my professional career.

[Flaze07]

instead of writting readable code you should be hardcore and write a spaghetti code

[dhayden]

why use recursion and not loop instead ??

It's recursive because it needs to store the position of each guess so it can undo it if necessary. You need a LIFO data structure of some sort and the call stack is the most convenient.

[jonnin]

Excellent point about how the code works. Vectors can play at being a simple stack, so that is not saving a ton of coding effort here.

[Golden Lizard]

Here's how recursion works: it adds stackframe over stackframe until it gets to the deepest level (i.e: there is a result). Consider the following function:

int recursion(unsigned i)
{
    return i == 0 ? 1 : recursion(i-1) + 1;
}
//........... using the function
recursion(5);

So now, a stackframe is added:

--STACK--
recursion(5)

And as it continues, the height of the stack will grow.

--STACK--
recursion(1)
recursion(2)
recursion(3)
recursion(4)
recursion(5)

It will finally stop when it hits a result

--STACK--
recursion(0) => returns 1 ("palpable" result)
recursion(1)
recursion(2)
recursion(3)
recursion(4)
recursion(5)

Now it will work from top to bottom, poping stackframes, calculating the result for every previous call now that it has something to start from.

--STACK--
recursion(0) => returns 1 ("palpable" result), pops stackframe
recursion(1) => recursion(0) + 1 = 1+1 = 2, pops stackframe
recursion(2) => and it continues
recursion(3)
recursion(4)
recursion(5)

Until it calculates the result of the original call (which is recursion(5)) and returns it.

Now some points about recursion:
* not very efficient in C-like languages (there are some exceptions though)
* pay attention if you pass arguments as references
* most of the time, a recursive algorithm may be implemented in a iterative way or using a stack data structure, both of which are less prone to overflow
* in C, you can use recursion to simulate a stack (since you actually use a stack when doing recursive calls), but there's no reason to use it as such in C++ since you already got std::stack