Recursive stack overflow

[jems5]

My attempt to write a recursive method to produce the results of the number of combination where x=13 and y=52 and Combination (y, x) =.....

When I use small numbers (e.g.: 2,4) I tend to get a result only when I blank out the 3rd if statement. The formula used below was provided. I also get OverFlowStack error. The code below maybe be weak and I seek help to fix.

public class BridgeGame {
   
   // Need to solve for x=13 and y=52    
      static long x;
      static long y;
   
      public long Combinations(long x, long y) {
      
      // The base case      
         if (x == 1)
            return y;
         if (x == y)
            return 1;
         if (y > x > 1) // Boolean, int error here
      // The general case
         return (Combinations(y-1, x-1) + Combinations(y-1, x));

      }
   
   // Print results of possible combinations
      public void print() {
         System.out.println(Combinations(y, x));
      }
   	   
      public static void main (String[] args) {
         BridgeGame out = new BridgeGame();
         Scanner in = new Scanner(System.in);
         System.out.println("Please enter X value:");
         out.x = in.nextInt();
         System.out.println("Please enter Y value:");
         out.y = in.nextInt();
      	
         out.print();
      }
   }

[JamesCherrill]

y > x > 1
y > x
returns a boolean (true/false), so then it continues
boolean > 1
which is invalid - you can't compare a boolean and an int.
You need to compare y with x, then compare x with 0, then "and" the two results together
ie (in pseudo code)
(x greater than y) and (y greater than 0)

[jems5]

y > x > 1
y > x
returns a boolean (true/false), so then it continues
boolean > 1
which is invalid - you can't compare a boolean and an int.
You need to compare y with x, then compare x with 0, then "and" the two results together
ie (in pseudo code)
(x greater than y) and (y greater than 0)

Ah, I see that error. One other thing and that is how is it that I get missing return statement error when clearly there is one? I am thinking to myself an else should be squeezed in somewhere but I am not getting why.

public long Combinations(long x, long y) {
      
      // The base case      
         if (x == 1)
            return y;
         if (x == y)
            return 1;
         if (x > y && y > 0)
         // The general case
            return (Combinations(y-1, x-1) + Combinations(y-1, x));
      } // Missing return statement error here

[JamesCherrill]

Your return is part of the if statement starting on line 8, so if that if test is false the code drops thru line 11, where the method terminates without executing a valid return statement.

[jems5]

Your return is part of the if statement starting on line 8, so if that if test is false the code drops thru line 11, where the method terminates without executing a valid return statement.

If I understand you correctly, then I need an else statement. My revised code below produces a result with no OverFlowStacking error but the result is incorrect. Using a calculator the result should be = 635,013,599,600

The result was 188416 and returned a result in just seconds. According to clues given by the instructor this should take a while to resolve. Please critique the code and please advise where I am going wrong?

Thanks again JamesCherryll.

public class BridgeGame {
   
   // Need to solve for x=13 and y=52    
      static long x;
      static long y;
   
      public long Combinations(long x, long y) {
      
      // The base case      
         if (x == 1)
            return y;
         if (x == y)
            return 1;
         if (x > y && y > 0)
         // The general case
            return (Combinations(y-1, x-1) + Combinations(y-1, x));
         else
            return Combinations(y, x);
      }
   
   // Print results of possible combinations
      public void print() {
         System.out.println(Combinations(y, x));
      }
   	   
      public static void main (String[] args) {
         BridgeGame out = new BridgeGame();
         Scanner in = new Scanner(System.in);
         System.out.println("Please enter X value:");
         out.x = in.nextInt();
         System.out.println("Please enter Y value:");
         out.y = in.nextInt();
      	
         out.print();
      }
   }

[JamesCherrill]

Sorry, but I don't know what algorithm you are trying to implement. Can you give a brief english-language version?

ps I hope your final else never gets executed - it just calls recursively with the same parameters -> stack overflow. If that's a "not expected to happen" case it 's safer to print a little error message and return 0.

[jems5]

Sorry, but I don't know what algorithm you are trying to implement. Can you give a brief english-language version?

How many possible bridge hands are there? How many combination of x items can be made out of y items where x=13 and y=52 (like a deck of cards). The job is to write a recursive method that calculates the number of combination of x items out of y items. Then write a driver to print result.

Thanks,
Jems

[JamesCherrill]

OK, but what's the recursive algorithm, in english?

[jems5]

OK, but what's the recursive algorithm, in english?

Good question, I don't know how to answer that specific question. In math the quick formula is fact(52)/((fact(13)^4)). What I wrote is all the information I get to solve the problem. The other thing that might help me is knowing how to play bridge which I don't so I guess knowing the rules would help me answer the algorithm question...here I thought I understood the assignment task.

Thanks,
Jems

[JamesCherrill]

I think this just ceased to be a Java problem! I'm not being funny, but without a definition of the algorithm there's no way to code or debug an implementation of that algorithm. Trial & error may work, if you're very lucky, but probably not.
I guess this algorithm must be fairly standard, so it shouldn't be too hard to find it in Google-land.

[jems5]

I think this just ceased to be a Java problem! I'm not being funny, but without a definition of the algorithm there's no way to code or debug an implementation of that algorithm. Trial & error may work, if you're very lucky, but probably not.
I guess this algorithm must be fairly standard, so it shouldn't be too hard to find it in Google-land.

I guess you may be right and since I don't know the game I should start the Google search as you suggest.

Thanks again JamesCherryll and I will come back with more questions after my Google search.

[JamesCherrill]

OK. I have people arriving for dinner in 5 mins, so I;ll be offline until tomorrow.