text: A friendly place for programming greenhorns!
  Big Moose Saloon
  Search
  |
  Java FAQ
  |
  Recent Topics
  |
  Flagged Topics
  |
  Hot Topics
  |
  Zero Replies
  Register / Login
  JavaRanch
  »
  Java Forums
  »
  Java
  »
  Beginning Java
  Author
  Why does this recursion try each permutation?
  Yeuan Chen
  Greenhorn
  Joined: Jun 05, 2009
  Posts: 2
  posted
  Jun 05, 2009 21:41:53
  0
  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:
  public class Queens { public static boolean isConsistent(int[] q, int n) { for (int i = 0; i < n; i++) { if (q[i] == q[n]) return false; // same column if ((q[i] - q[n]) == (n - i)) return false; // same major diagonal if ((q[n] - q[i]) == (n - i)) return false; // same minor diagonal } return true; } public static void printQueens(int[] q) { int N = q.length; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (q[i] == j) System.out.print("Q "); else System.out.print("* "); } System.out.println(); } System.out.println(); } public static void enumerate(int N) { int[] a = new int[N]; enumerate(a, 0); } /*********************************************************************** * This following method is the part I am confused about. ***********************************************************************/ public static void enumerate(int[] q, int n) { int N = q.length; if (n == N) printQueens(q); else { for (int i = 0; i < N; i++) { q[n] = i; if (isConsistent(q, n)) enumerate(q, n+1); } } } public static void main(String[] args) { int N = Integer.parseInt(args[0]); enumerate(N); } }
  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
  posted
  Jun 06, 2009 00:01:42
  0
  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
  I like...
  posted
  Jun 06, 2009 00:42:15
  0
  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
  posted
  Jun 06, 2009 09:43:08
  0
  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
  posted
  Jun 06, 2009 21:53:59
  0
  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
  I like...
  posted
  Jun 06, 2009 22:39:19
  0
  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:
  subject: Why does this recursion try each permutation?
  Similar Threads
  what does this mean?
  Loops
  A Basic For Loop??
  Java Code
  Determining whether a queen can attack another piece
  All times are in JavaRanch time: GMT-6 in summer, GMT-7 in winter
  JForum
  |
  Paul Wheaton