Win a copy of Java EE 8 High Performance this week in the Java/Jakarta EE forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Why does this recursion try each permutation?

Greenhorn
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?

Ranch Hand
Posts: 686
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

Author
Rancher
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
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.

Greenhorn
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
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*.

 It is sorta covered in the JavaRanch Style Guide.