CODEWITHSUNDEEP
javarecursion
Bart g
Bart g

Reputation: 585

Recursion Additionpuzzle in java

I am working on a project since we are starting to studying recursion. I am very new on this so I am not sure how to tackle this puzzle. This is the problem in the book and I would appreciate any STEPS(step1, step2, ...) that may help me to come up with ideas to solve this problem ALSO, I really appreciate if any one can share with me a way to understand recursion, still it does not make a lot of sense to me so I would appreciate any advice on how to understand better this topic. Ok, so these are the instructions. Thank you.

An AdditionPuzzle has a form such as 2BCD+BCDE=DA01. We want to find all solutions, where A, B, C, D are distinct digits, different from any digits in the puzzle. Here, a solution is 2345+3456=5801. In general, a puzzle can have any combination of up to ten digits and numbers. Write a recursive method for computing a solution to a puzzle using these two classes:

Class #1

public class ThisPuzzle
{ 
 /**
  Returns a solution to a puzzle.
  @param p a puzzle
  @return a solution or null if none exists
 */
public static Puzzle solvePuzzle(Puzzle p)
{
  // ...
  return null;
}

 public static void main(String[] args) 
{
  Puzzle p = new Puzzle("3A6", "36B", "71C");
  System.out.println(solvePuzzle(p));
}
}

Class #2

public class Puzzle 
{
   private String add1;
   private String add2;
   private String result;

   /**
      Constructs a puzzle.
      @param add1 a string containing digits 0 - 9 and letters
      @param add2 a string containing digits 0 - 9 and letters
      @param result a string containing digits 0 - 9 and letters
   */
   public Puzzle(String add1, String add2, String result) 
   {
      this.add1 = add1;
      this.add2 = add2;
      this.result = result;
   }

   /**
      Makes a new puzzle by replacing a letter with a digit.
      @param letter the letter to be replaced
      @param digit the digit to replace it with
      @return the new puzzle
    */
   public Puzzle replace(String letter, int digit)
   {
      // ...
   }

   /**
      Returns true if the puzzle is solved.
      @return true if the puzzle has no letters and the 
      first two numbers add up to the third
   */
   public boolean isSolved() 
   {
      // ...
   }

   /**
      Gets the first letter in this puzzle.
      @return the first letter, or "" if there are no letters.
   */
   public String firstLetter()
   {
      // ...
   }

   /**
      Checks whether this puzzle contains a given digit.
      @param digit a digit
      @return true if this puzzle returns digit
   */
   public boolean contains(int digit)
   {
      // ...
   }

   public String toString()
   {
      return add1 + "+" + add2 + "=" + result;
   }    
}

Upvotes: 3

Views: 401

Answers (1)

roby
roby

Reputation: 3273

Recursion is when you call a method inside it's own definition.

A very simple infinite recursion is:

public static void recurse(){
    recurse();
}

Calling this method will cause a stack overflow exception. It might be easier to imagine why there would be an error if you print a message inside recurse.

public static void recurse(){
    recurse();
    System.out.println("finished recursing")
}

An error will be thrown before you hit the print because the machine has to maintain a stack of all the method calls in the vain hope that the inner recursion will finish and it can print you a message.

For your problem you will need to call solvePuzzle within solvePuzzle. The idea is that you should attempt to solve easier Puzzle inside each level of recursion. Think trial and error.

Upvotes: 2

Related Questions