macOS Help with Java Recursion Program

[j0hnnys]

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:

public static void sortStr(String first, String second) {
    //?????????????????????????????????????????
    }

So any help?

 

[sammich]

I suggest the following code:

public static void sortStr(String first, String second) {
	try {
		doingyourhomework();
	}
}

Just so I don't look like a bastard, the hint is in:

The stopping case of the method occurs when the length of first has zero characters

 

[j0hnnys]

public static void sortStr(String first, String second) {
	try {
		doingyourhomework();
	}
        catch {
                studyingForCalcFinals(whichI, suckAt);
        }
}

 

[ulbador]

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.

 

[lee1210]

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

 

[ulbador]

Also, keep in mind that Java passes all objects by reference.

 

[lee1210]

Also, keep in mind that Java passes all objects by reference.

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

 

[j0hnnys]

Okay, so far I've got this:

    public static void strRe(String first, String 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(first, second);
        }
    }

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.

 

[ulbador]

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

True. Didn't pay attention to the fact that it was static.

To the OP: Recursion means a method that calls itself.

 

[lee1210]

Okay, so far I've got this:

    public static void strRe(String first, String 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(first, second);
        }
    }

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.

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?

 

[j0hnnys]

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

 

[MaynardJames]

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

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.

 

[vocaro]

Also, keep in mind that Java passes all objects by reference.

Incorrect. Java is pass-by-value. Always.

 

[lee1210]

Incorrect. Java is pass-by-value. Always.

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

 

[ulbador]

Incorrect. Java is pass-by-value. Always.

For objects that value is the address, so... it can be argued. It's not an argument worth having, though.

This should demonstrate:

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:

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.

 

[jared_kipe]

This should demonstrate:


//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);
}

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();"

 

[vocaro]

As mentioned, it's not "true" pass by reference such as in C

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.

 

[uwbadger]

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:

/* 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:

/* 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);
    }
}

 

[jared_kipe]

// self-assignment is okay
Foo& operator=(const Foo& f) { _data = f._data; }

[/code]

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

    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.

 

[uwbadger]

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)

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.

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

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.

 

[vocaro]

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

Please see: http://javadude.com/articles/passbyvalue.htm

 

[jared_kipe]

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)