Thread: limit on recursion?

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    36

    limit on recursion?

    Hey guys

    I have programmed a brute force sudoku solver. However, whilst it is fine for some of the easier puzzles, it seems to randomly stop half way through for the hard ones.

    Im not sure, but could this be because I am using a lot of recursion? If i understand correctly, everytime you call recursion it eats away at memory. Could my program be stopping itself automatically due to some sort of overflow?

    If so, is there any way around this?

    Many thanks

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    There is no explicit limit to the number of recursions you can make, but there is a limit to the amount of stack-space you can use up - that's about 2MB on Windows (by default - , but can be smaller or larger in other systems. Using microsoft tools, you can change the stack-size by giving a larger size with the /STACK option - but there's a limit somewhere to how far you can go.

    Edit: But the way around it is to either avoid deep recursion, or "don't store big things on the stack while recursing" [for example, don't make another copy of the Sudoku board every recursion, or if you have to do that, make it using "new" rather than as a local variable.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Mar 2008
    Posts
    36
    Ok nice. I think i will change the stack sizes and check how far the brute force solver will go.

    Just to give an idea, I am recursing the function 'force' very many times

    Code:
    void force(int puzzle_grid[9][9],nodeptr pointer_array[9][9],coordptr coords_array[9][9],int xcoord, int ycoord,coordptr searchptr,int value)
    So it has the puzzle board, two arrays of list pointers, three integers and a pointer);
    is this considered excessive? I havn't had much programming experience.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Well, each [9][9] array will only take up 4 bytes, as it turns into a pointer, so with 7 arguments, the total of your arguments is 28 bytes + whatever the compiler needs for internal use, so say 48 bytes to be on the safe side - that would allow you several thousand recursions - about 40000 if you haven't got any huge local variables.

    But you also have to add any local variables in the function itself, for example local copies of the board.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Instead of using function recursion and the program stack, implement the algorithm using a common loop and std::stack with push_back/pop_back etc...
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  6. #6
    Registered User
    Join Date
    Mar 2008
    Posts
    36
    Oh dear. I did some debugging on visual c++ and when the program ends earlier than it should its either due to a memory violation or stack overflow.

    There must be quite a serious fault in my code. When inputting a completely blank sudoku, it gets a stack overflow after finding 3 solutions. A blank sudoku should have billions of solutions >.< my computer should be finding them all day long!

    Whenever the program stops it is always at the same place.

    Code:
    coordptr searchptr = coords_array[xcoord][ycoord];
    while (searchptr->next !=NULL){
    	xcoord = searchptr->xcoord;
    	ycoord = searchptr->ycoord;
    		for(int number=1 ;number<10; number++){
    				nodeptr newnode = new node;
    				newnode->number = number;
    				newnode->next = pointer_array[xcoord][ycoord];
    				pointer_array[xcoord][ycoord] = newnode;
    				}
    		searchptr = searchptr->next;
    }
    It is always on the line
    Code:
    nodeptr newnode = new node;
    This piece of code is from a function which is called every time the program effectively does a backtrack.
    I call a function which deletes every node from an array of pointers and then i remake the lists using the function above.

    Is it very wrong to make lists within lots of recursion.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    It is not wrong to make lists within recursion, but if you run out of memory, or overwrite the end of your buffer, then you will get the problems you are describing.

    It sounds like you are running out of memory to me.

    Running out of stack due to too much recursion will also lead to INSTANT death of the application. If you have a look at the register view, and check ESP, see what it is in main, then whenever it's crashed, check if it's about 0x200000 lower - that's out of stack in default stack-size.

    Almost all recursive algorithms can be written using linear iteration.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Registered User
    Join Date
    Mar 2008
    Posts
    36
    I think you're right, I took a bit of time replacing my recursion needs with while loops. No longer get stack overflows! I guess recursion was just in my head from just having done it on my course hehe

    However, still can't solve every sudoku - have found what appears to be a bug

    Thanks for all the help!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. Recursion
    By Lionmane in forum C Programming
    Replies: 11
    Last Post: 06-04-2005, 12:00 AM
  3. Replies: 3
    Last Post: 01-08-2004, 09:43 PM
  4. hi need help with credit limit program
    By vaio256 in forum C++ Programming
    Replies: 4
    Last Post: 04-01-2003, 12:23 AM
  5. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM