Help with Java Recursion Program

Discussion in 'Mac Programming' started by j0hnnys, Dec 13, 2010.

  1. j0hnnys, Dec 13, 2010
    Last edited: Dec 13, 2010

    j0hnnys macrumors member

    Joined:
    Aug 18, 2010
    Location:
    California
    #1
    I need some help on the following java program:

    Write a recursive method that has two parameters, first and second, that are both strings. The method should print all rearrangements of the letters in first followed by second. For example, if first is the string "CAT" and second is the string "MAN", then the method would print the strings CATMAN, CTAMAN, ACTMAN, TACMAN, and TCAMAN. The stopping case of the method occurs when the length of first has zero characters. We'll leave the recursive thinking up to you. It also give tips to use the substring method for strings.

    It's just one of those basic problems where I feel I'm not thinking abstractly enough. So far I'm just stuck at:
    PHP:
    public static void sortStr(String firstString second) {
        
    //?????????????????????????????????????????
        
    }
    :( So any help?
     
  2. sammich macrumors 601

    sammich

    Joined:
    Sep 26, 2006
    Location:
    Sarcasmville.
    #2
    I suggest the following code:

    PHP:
    public static void sortStr(String firstString second) {
        try {
            
    doingyourhomework();
        }
    }
    Just so I don't look like a bastard, the hint is in:

     
  3. j0hnnys thread starter macrumors member

    Joined:
    Aug 18, 2010
    Location:
    California
    #3
    PHP:
    public static void sortStr(String firstString second) {
        try {
            
    doingyourhomework();
        }
            catch {
                    
    studyingForCalcFinals(whichIsuckAt);
            }
    }
     
  4. ulbador macrumors 68000

    ulbador

    Joined:
    Feb 11, 2010
    #4
    I would read up about what recursion actually means when it comes to calling methods. You seem to lack even that basic tidbit considering all you copied was a basic method declaration.
     
  5. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #5
    For every character in string one, do something with it, call self with new arguments. I'd consider string one being one character long being a base case along with length 0.

    Seems like fun. If my phone had a compiler I might work it out.

    Remember that you need to work toward a base case with every iteration.

    -Lee
     
  6. ulbador macrumors 68000

    ulbador

    Joined:
    Feb 11, 2010
    #6
    Also, keep in mind that Java passes all objects by reference.
     
  7. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #7
    If the prototype given is required, the arguments are java.lang.String and immutable, so this doesn't make much of a difference in this case.

    -Lee
     
  8. j0hnnys thread starter macrumors member

    Joined:
    Aug 18, 2010
    Location:
    California
    #8
    Okay, so far I've got this:
    PHP:
        public static void strRe(String firstString second) {
            
    System.out.println(first+second);
            if(
    second.length()>0) {
                
    first first second.charAt(second.length()-1);
                
    second second.substring(0,second.length()-1);
                
    strRe(firstsecond);
            }
        }
    but it only outputs 4 lines containing 3 different lines when I enter "CAT" as the parameter for first, and "MAN" as the parameters for second.
     
  9. ulbador macrumors 68000

    ulbador

    Joined:
    Feb 11, 2010
    #9
    True. Didn't pay attention to the fact that it was static.

    To the OP: Recursion means a method that calls itself.
     
  10. lee1210, Dec 13, 2010
    Last edited: Dec 13, 2010

    lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #10
    String 2 should grow, string 1 shrinks. You only need to print in the base case, not unconditionally. You can't just peel the last character off and recurse. In a post above I said to do something with each character of string 1. This implies a loop. It took me five or so minutes to type the pseudocode on my phone, but it's not pseudo enough to post. There was a single action to perform when string 1 was length 0 or 1(base case). I had three recursive cases to simplify the substr logic.

    -Lee

    Edit:
    Ran your code "on paper" and got:
    String1 cat
    String2 man
    Print catman
    Str1 = cat + n
    Str2 = ma
    Print catnma
    Str1=catn+a
    Str2 = m
    Print catnam
    Str1 = catna+m
    Str2=*
    Print catnam
    End

    Did you? What seems to be wrong?
     
  11. j0hnnys thread starter macrumors member

    Joined:
    Aug 18, 2010
    Location:
    California
    #11
    "The stopping case of the method occurs when the length of first has zero characters."
    With n as the length of the string, there will always be n different outputs. Am I right?
     
  12. MaynardJames, Dec 14, 2010
    Last edited: Dec 14, 2010

    MaynardJames macrumors newbie

    Joined:
    Aug 27, 2008
    #12
    No. The example given in the question should have already told you this is not the case (although the example itself is flawed as it is missing one arrangement, ATCMAN). Finding all the rearrangements (not the best use of words chosen by the instructor if this is indeed a school assignment) is simply finding the permutations of said string. To do this, you simply use factorials to figure out how many outputs there would be. With string length n, there should be n! (n factorial) outputs. Indeed, with the string CAT (length 3), there are 3! (3x2x1=6) outputs.

    I suggest, as others have, that you do some research on recursion (ie. base cases, recursive cases). By the code you have posted, its quite obvious that you don't understand the concepts of recursion yet, so thats your best bet.
     
  13. vocaro macrumors regular

    Joined:
    Mar 5, 2004
    #13
    Incorrect. Java is pass-by-value. Always.
     
  14. lee1210, Dec 14, 2010
    Last edited: Dec 14, 2010

    lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #14
    For objects that value is the address, so... it can be argued. It's not an argument worth having, though.

    To the OP:
    I've said it a few times already, but I'll try again.
    In your base case, print and return.
    In your recursive case, loop from 0 to the length of str1 - 1.
    In each iteration of your loop you will call the function again.
    When you call your function from itself, str1 should be one character shorter and str2 should be one character longer.

    -Lee
     
  15. ulbador macrumors 68000

    ulbador

    Joined:
    Feb 11, 2010
    #15
    This should demonstrate:

    Code:
    import java.util.Vector;
    
    public class Testcase {
    
    
        public static void main (String[] args) {
            Testcase tc = new Testcase();
        }
    
        public Testcase () {
            int intVal = 1;
            String strVal = "Test";
            Vector vecVal = new Vector();
            vecVal.add(strVal);
    
    
            //Ints are passed by value:
            System.out.printf("Int before: %d\n",intVal);
            intTest(intVal);
            System.out.printf("Int after: %d\n",intVal);
    
            //Strings are passed by reference, but immutable
            System.out.printf("Str before: %s\n",strVal);
            strTest(strVal);
            System.out.printf("Str after: %s\n",strVal);
    
            //Vectors passed by reference
            System.out.printf("Vector size before: %d\n",vecVal.size());
            vecTest(vecVal);
            System.out.printf("Vector size after: %d\n",vecVal.size());
    
        }
    
    
        //Ints passed by value
        public void intTest(int incomingInt) {
            incomingInt+=10;
        }
    
        //Strings are immutable, effectively passed by value
        public void strTest(String incomingStr) {
            incomingStr = incomingStr + "Test";
        }
    
        //Vectors and 99% of other objects, passed by reference
        public void vecTest(Vector incomingVec) {
            String newStr = "TestTestTest";
            incomingVec.add(newStr);
        }
    
    
    }
    
    
    Output:
    Code:
    Int before: 1
    Int after: 1
    Str before: Test
    Str after: Test
    Vector size before: 1
    Vector size after: 2
    
    As mentioned, it's not "true" pass by reference such as in C, but it is for demonstration's sake.
     
  16. jared_kipe macrumors 68030

    jared_kipe

    Joined:
    Dec 8, 2003
    Location:
    Seattle
    #16
    This dilutes what is actually going on here. in strTest you overwrote your pointer to incomingStr to be a NEW string object. The original string object is still referenced by the calling object.

    To make this analogous in your vecTest you would need to put something like "incomingVec = new Vector();"
     
  17. vocaro macrumors regular

    Joined:
    Mar 5, 2004
    #17
    C does not support pass-by-reference. Like Java, parameters are always passed by value. And your example does not demonstrate pass-by-reference.

    Software engineering is hard enough without us being ambiguous with definitions (true vs. almost true). Let us be precise and avoid confusion.
     
  18. uwbadger, Dec 14, 2010
    Last edited: Dec 14, 2010

    uwbadger macrumors member

    Joined:
    May 20, 2009
    #18
    Here's an example showing the difference between passing-by-reference (C++) and passing a "reference" (pointer!) by-value (Java). In C++, the swap method works correctly:

    Code:
    /* Output:
    % g++ Foo.cc
    % ./a.out
    10, -10
    -10, 10
    */
    
    #include <iostream>
    using namespace std;
    
    class Foo
    {
    public:
        Foo(int x) : _data(x) {}
        Foo(const Foo& f) : _data(f._data) {}
    
        // EDIT: Removed explicit assignment operator, since (as Jared points out),
        // it's cheating.
        // Foo& operator=(const Foo& f) { _data = f._data; }
    
        ~Foo() {}
    
        friend ostream& operator<<(ostream& out, const Foo& f);
    private:
        int _data;
    };
    
    ostream& operator<<(ostream& out, const Foo& f)
    {
        out << f._data;
        return out;
    }
    
    void swap(Foo& f1, Foo& f2)
    {
        Foo temp = f1;
        f1 = f2;
        f2 = temp;
    }
    
    int main()
    {
        Foo a(10);
        Foo b(-10);
        cout << a << ", " << b << "\n";
        swap(a,b);
        cout << a << ", " << b << "\n";
        return 0;
    }
    


    In Java, swap appears to work correctly inside the swap() method itself, but it doesn't actually work, because the Foo objects are not passed by reference:

    Code:
    /* Output:
    % javac Foo.java
    % java Foo
    10, -10
    Inside swap 10, -10
    Inside swap -10, 10
    10, -10
    */
    
    public class Foo
    {
        public Foo(int x) { _data = x; }
        public String toString ()
        {
            return "" + _data;
        }
    
        private int _data;
    
        public static void swap(Foo f1, Foo f2)
        {
            System.out.println("Inside swap: " + f1 + ", " + f2);
            Foo temp = f1;
            f1 = f2;
            f2 = temp;
            System.out.println("Inside swap: " + f1 + ", " + f2);
        }
    
        public static void main(String[] args)
        {
            Foo a = new Foo(10);
            Foo b = new Foo(-10);
            System.out.println(a + ", " + b);
            swap(a,b);
            System.out.println(a + ", " + b);
        }
    }
    
     
  19. jared_kipe macrumors 68030

    jared_kipe

    Joined:
    Dec 8, 2003
    Location:
    Seattle
    #19
    No offense, but this is cheating. You overloaded the = (assignment) operator to change the data inside the object into the data from the other object. The objects didn't literally switch place in physical memory. Only their internal values changed. (aka int _data)

    To achieve the same thing, albeit in a slightly less clever way would be

    Code:
        public static void swap(Foo f1, Foo f2)
        {
            System.out.println("Inside swap: " + f1 + ", " + f2);
            Foo temp = new Foo(0);
            temp.assign(f1);
            f1.assign(f2);
            f2.assign(temp);
            System.out.println("Inside swap: " + f1 + ", " + f2);
        }
        public void assign(Foo newFoo) {
            _data = newFoo._data;
        }
    

    The POINT is that passing by value essentially copies the original data into the function's memory space. Passing by reference copies a "reference" (aka address) to the function's memory space.

    The reason is two fold. #1 for primitive types/structs it is the only way to modify the original so that after the stack frame is popped the calling function has the change implicitly. #2 passing by "value" becomes more and more costly on both memory and processor the bigger whatever it is you're passing gets.

    Java cannot pass primitives by reference, and thus cannot take advantage of #1, all Objects are still passed by reference.
     
  20. uwbadger macrumors member

    Joined:
    May 20, 2009
    #20
    Ah, you're right. I was focused on the swap methods, and I wrote the (optimized) assignment operator as is standard for such an object. Fortunately, it still works just as well using a more generic assignment implementation. Just comment out the explicit assignment operator and use the compiler generated one.

    Nope, you're wrong there. Java does not pass-by-reference. Period. Objects are accessible only via handles (references), but these handles are always passed by value.
     
  21. vocaro macrumors regular

    Joined:
    Mar 5, 2004
    #21
  22. jared_kipe macrumors 68030

    jared_kipe

    Joined:
    Dec 8, 2003
    Location:
    Seattle
    #22
    Ah ok, apparently I've always though of, or been told, that pointers == reference and that they are practically synonymous. AND, I've always thought the important difference between pass by value and pass by reference is wether or not the actual the thing being passed was copied into the function or not. (yes I know that you copy the pointer to the object, but my point is you don't copy the literal object)
     

Share This Page