aspose file tools*
The moose likes Beginning Java and the fly likes Why does this recursion try each permutation? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Why does this recursion try each permutation?" Watch "Why does this recursion try each permutation?" New topic
Author

Why does this recursion try each permutation?

Yeuan Chen
Greenhorn

Joined: Jun 05, 2009
Posts: 2
I am having trouble following why after completing the for loop with no placement, the program automatically decreases n by one and tries again. I've noted the section I am confused about with asterisks.

From http://www.cs.princeton.edu/introcs/23recursion/Queens.java.html:



Trying to understand what it's doing, I tried it for 4 queens, and added a System.out.println(q[n]) and System.out.println(n) in the enumerate method. What it told me was that n starts at 0, it places q[0] = 0, and sets n = 1 (everything's okay so far). It then sets q[1] = 2, and n =2. However, it tries n = 2 four times (as specified in the loop), and it doesn't check out, and then it sets n = 1. This is where I am confused. I understand why it would want to do so (as q[1] =2 apparently is not a good final placement), but I don't understand where in the code it tells it to decrease the n and try other permutations? Thanks for your help.

Edited:
Also, how does it know not to try the same placements, like q[1] = 2 again, and not get stuck in a loop?
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
Posts: 679
didn't anyone ever explain to you that trying to understand how/why recursion works is detrimental to your sanity?


p.s. sorry Yeuan, I couldn't resist
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

Last question first: why *would* it try the same combination again? In other words, play computer for a little bit: run it "by hand", writing down the conditions and the steps being taken. Pay particular attention to when the recursion happens, and when it returns.

Subject question next: because you told it to!

First sentence last: the program doesn't decrease n at all, anywhere. The value of n only increases--the trick is to understand why you're seeing lower values sometimes. It's not because n has decreased in value... it's because you're looking at an old value of n.

It's really not all that difficult, but can sometimes take some mental effort to get over the initial confusion... hopefully those hints are enough to get you on the right track.
Yeuan Chen
Greenhorn

Joined: Jun 05, 2009
Posts: 2
My understanding of recursion must be flawed; what I thought would happen was this:

Let's say we do it for a 4x4 board. It calls on enumerate (the second one) the first time, inputting an int array, all null, of length 4, int n = 0. N is set to 4, n != N so it continues on to the for loop, at which point it sets q[0] = 0, which passes isconsistent, and therefore it calls upon enumerate again with the 0th element of the array equal to zero, and n = 1. Again, it gets to the for loop, sets q[1] to both i = 0 and i = 1, and finally i = 2 because isconsistent didn't check out for either i=0 or i=1. Calls upon enumerate with inputs int array q and n+1=2, and gets to the for loop again. Tries i=0, i=1, i=2, i=3, all of which don't pass isconsistent, and then (here's where I'm confused), I thought the method would terminate? The for loop would end, having reached i<4, and then the method...? But I'm obviously missing something here.

Unless...it branches off? When it runs n=1 it sets q[1] = 2, and enumerates with it, but instead of ending the for loop it also tries for 3 as well and then enumerates for that as well...? I don't know, I'm grasping at straws now.
james dunster
Greenhorn

Joined: May 03, 2009
Posts: 20
I find the best way of understanding these is to write down the ins and outs to the stack by hand. Good stuff pencil and paper.
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

The method *does* terminate--but your program doesn't just stop running, it continues from where the method was called. Over and over. Until the *original* loop terminates.

Seriously--do it by hand, on paper--we're not just telling you that for fun. It's a valuable exercise, and will most likely clear up your confusion. You're making a set of *nested* calls--when each call terminates it returns back to where it was before the call and *keeps on going*.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Why does this recursion try each permutation?