-1

I would like to ask if it is really necessary to track every recursive call when writing it, because I am having troubles if recursive call is inside a loop or inside multiple for loops. I just get lost when I am trying to understand what is happening. Do you have some advice how to approach recursive problems and how to imagine it. I have already read a lot about it but I havent found a perfect answer yet. I understand for example how factorial works or fibonacci recursion. I get lost for example when I am trying to print all combinations from 1 to 5 length of 3 or all the solutions for n-queen problem

Zokav
  • 19
  • 1
  • 3
  • 1
    You need to give a very concrete example of what you're trying to understand, and what you don't understand. – Eric Duminil Jul 09 '17 at 10:02
  • Possible duplicate of [How to think in recursive way?](https://stackoverflow.com/questions/17611275/how-to-think-in-recursive-way) – smoe Jul 09 '17 at 10:08
  • Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation. [on topic](http://stackoverflow.com/help/on-topic) and [how to ask](http://stackoverflow.com/help/how-to-ask) apply here. StackOverflow is not a design, coding, research, or tutorial service. – Prune Jul 10 '17 at 16:12

2 Answers2

1

I had a similar problem, try drawing a tree like structure that keeps track of each recursive call. Where a node is a function and every child node of that node is a recursive call made from that function.

Ninji
  • 5
  • 4
  • I have been trying to do so, but it is hard to draw it for me when problem is more complicated – Zokav Jul 09 '17 at 10:10
  • @Zokav in that case I'd say you have to give a more concrete example or you could try writing a program that draws the tree for you. – Ninji Jul 09 '17 at 10:22
1

Everyone may have a different mental approach towards towards modeling a recursive problem. If you can solve the n queens problem in a non-recursive way, then you are just fine. It is certainly helpful to grasp the concept of recursion to break down a problem, though. If you are up for the mental exercise, then I suggest a text book on PROLOG. It is fun and very much teaches recursion from the very beginning.

Attempting a bit of a brain dump on n-queens. It goes like "how would I do it manually" by try and error. For n-queens, I propose to in your mind call it 8-queens as a start, just to make it look more familiar and intuitive. "n" is not an iterator here but specifies the problem size.

  • you reckon that n-queens has a self-similarity which is that you place single queens on a board - that is your candidate recursive routine
  • for a given board you have a routine to test if the latest queen added is in conflict with the prior placed ones
  • for a given board you have a routine to find a position for the queen that you have not tested yet if that test is not successful for the current position
  • you print out all queen positions if the queen you just placed was the nth (last) queen
  • otherwise (if the current queen was validly placed) you position an additional queen

The above is your program. Your routine will pass a list of positions of earlier queens. The first invocation is with an empty list.

smoe
  • 500
  • 3
  • 13