SRL Archive - Help and Support

Sorry can't post this in regular section, as there is a snippet of my code and my teacher will google my code and it will show up here (happened last time >.<)

I really need help here, I don't understand what it is asking of me or how to use recursion to solve the problem (I just don't see recursion as useful ever)

Project one
Here is my semi completed solution, what can I do to completely make it work?

public class Recursive {
	public static void printLetterPattern(char c)
{
	if(c == 'A')
			System.out.print('A');
	else
	{
		switch(C)
		{
		case 'B': printLetterPattern('A');
		break;
		case 'C': printLetterPattern('B');
		break;
		case 'D': printLetterPattern('C');
		break;
		case 'E': printLetterPattern('D');
		break;
		case 'F': printLetterPattern('E');
		break;
		case 'G': printLetterPattern('F');
		break;
		case 'H': printLetterPattern('G');
		break;
		case 'I': printLetterPattern('H');
		break;
		case 'J': printLetterPattern('I');
		break;
		case 'K': printLetterPattern('J');
		break;
		case 'L': printLetterPattern('K');
		break;
		case 'M': printLetterPattern('L');
		break;
		case 'N': printLetterPattern('M');
		break;
		case 'O': printLetterPattern('N');
		break;
		case 'P': printLetterPattern('O');
		break;
		case 'Q': printLetterPattern('P');
		break;
		case 'R': printLetterPattern('Q');
		break;
		case 'S': printLetterPattern('R');
		break;
		case 'T': printLetterPattern('S');
		break;
		case 'U': printLetterPattern('T');
		break;
		case 'V': printLetterPattern('U');
		break;
		case 'W': printLetterPattern('V');
		break;
		case 'X': printLetterPattern('W');
		break;
		case 'Y': printLetterPattern('X');
		break;
		case 'Z': printLetterPattern('Y');
		System.out.print(c);
		}
	}
}
}

Here is the second assignment (the one I don't understand at all)



PLEASE help me solve these, I honestly am dumbfounded (been staring at them for the past hour)

For the second one.
Can't you just check the index of each character in that string, and if they're not the same, delete it from the array, and if its the same, continue, then just count the remaining together?

I cant seem to compare chars, I tried .equals but to no avail. Is it ==?

Yeah.
I'll write up a program, give me a bit.

anIntValue.equals(anotherIntValue) ?

Bit beyond what I know in java but I like this as I'll prob see this soon/next quarter :)

From: Le Jingle
anIntValue.equals(anotherIntValue) ?

Bit beyond what I know in java but I like this as I'll prob see this soon/next quarter :)

Yeah that is what I tried earlier didn't work for me.

Can't you also use a loop some how for the char part in #1?

Like 'A' is equal to 65 integer value, and iirc you can do
for (int i = 0; i < char; i++) {
System.out.println(char);
}

because 'A' single chars can be used as int values too I think? Sorry, not to knowledgeable but I'm still taking a shot at the problem #1

'A' = 65, 'B' = 66, … 'Z' = 90

then maybe cast back the ints to chars?

*can't seem to understand recursion

For the first one: make a while loop for c > 65. Then keep looping one method and decrease c. Off to driving lesson soon when I get back I'll write the code. What year/semester is this?

College freshman year, first semester java introduction course

From: [XoL]
College freshman year, first semester java introduction course

I see, I got all the results of my first semester now and passed all exams including Programming theory/practical with a 10. This is quite a lot harder than we had, though. I guess you still need help with this so I'm going to work on it now :)

Think I managed to understand the 'logic' now:

D, C, B, A

B: AB
C: AC AB
D: D + ABACAB

This is what I came up with in like, a hour or two of fiddling with it.
Edit: I read the problem wrong. Removed code, will fix when I return from school.

That's not really recursion NKN? :P
EDIT: That is the 2nd part I guess?

Here is what I came up with.

public class LetterPattern {
	
	public static void printLetterPattern(char c){
		int value = Integer.valueOf(c);
		//System.out.println("Start value of c: " + value);
		
		String temp = "";
		for(int i = 97; i < value; i++){
			char tempChar = (char) i;
			if(tempChar == 'a'){
				temp = "a";
			}else{
				temp = temp + tempChar + temp;
			}
		}
		
		String output = (temp + c + temp).toUpperCase();
		System.out.println("Output: " + output);
	}
	
	public static void main(String[] args){
		System.out.println("Type your character");
		Scanner in = new Scanner(System.in);
		char inputChar = in.next().charAt(0);
		//System.out.println("Input character: " + inputChar);
		printLetterPattern(inputChar);
	}
}

Type your character
b
Output: ABA

Type your character
d
Output: ABACABADABACABA

Type your character
f
Output: ABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABA

Not sure if the other outputs are correct but A, B, C, D are so I guess F is correct aswell.
Just used my brain to check if it is correct and I think it is. Now that it's solved the code looks much easier.. as always.

Type your character
k
Output: ABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAIABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAJABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAIABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAKABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAIABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAJABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAIABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABA

EDIT: Villavu adds spaces for some reason.

From: J J
That's not really recursion NKN? :P
EDIT: That is the 2nd part I guess?

Here is what I came up with.

public class LetterPattern {
	
	public static void printLetterPattern(char c){
		int value = Integer.valueOf(c);
		//System.out.println("Start value of c: " + value);
		
		String temp = "";
		for(int i = 97; i < value; i++){
			char tempChar = (char) i;
			if(tempChar == 'a'){
				temp = "a";
			}else{
				temp = temp + tempChar + temp;
			}
		}
		
		String output = (temp + c + temp).toUpperCase();
		System.out.println("Output: " + output);
	}
	
	public static void main(String[] args){
		System.out.println("Type your character");
		Scanner in = new Scanner(System.in);
		char inputChar = in.next().charAt(0);
		//System.out.println("Input character: " + inputChar);
		printLetterPattern(inputChar);
	}
}

Type your character
b
Output: ABA

Type your character
d
Output: ABACABADABACABA

Type your character
f
Output: ABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABA

Not sure if the other outputs are correct but A, B, C, D are so I guess F is correct aswell.
Just used my brain to check if it is correct and I think it is. Now that it's solved the code looks much easier.. as always.

Type your character
k
Output: ABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAIABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAJABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAIABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAKABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAIABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAJABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAIABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABA

EDIT: Villavu adds spaces for some reason.

That's not recursive. You'll get counted down for that.

Oh I see, recursive is something else than I thought it was. I still need to eat as I worked a bit on the 2nd one but I'm done with it now, if anyone else wants to finish it.

The idea

Code

public class CommonSubstring {
	
	public static int longComSubSeq(String str1, String str2){
		int mostMatches = 0;
		
		/*
		for(int i = 0; i < str1.length(); i++){
			for(int j = i; j < str1.length(); j++){
				int matches = 0;
				for(int k = 0; k < str2.length(); k++){
					if(str1.charAt(j) == str2.charAt(k)){
						matches++;
					}
				}
				if(matches > mostMatches){
					mostMatches = matches;
				}
			}
		}
		*/

		// Increasing chars @ str2
		for(int i = 0; i < str1.length(); i++){
			for(int j = 0; j < str2.length(); j++){
				if(str1.charAt(i) == str2.charAt(j)){
					int matches = 1;
					int k = i+1;
					
					
					for(int l = j+1; l < str2.length(); l++){
						if(k < str1.length()){
							if(str1.charAt(k) == str2.charAt(l)){
								matches++;
								k++;
							}
						}
					}

					System.out.println("i : " + i + ", j: " + j + " &  matches: " + matches);
					
					if(matches > mostMatches){
						mostMatches = matches;
					}
				}
				
				
			}
		}
		
		// Increasing chars @ str1
		for(int i = 0; i < str1.length(); i++){
			for(int j = 0; j < str2.length(); j++){
				if(str1.charAt(i) == str2.charAt(j)){
					int matches = 1;
					int k = j+1;

					for(int l = i+1; l < str1.length(); l++){
						if(k < str2.length()){
							if(str1.charAt(l) == str2.charAt(k)){
								matches++;
								k++;
							}
						}
					}

					System.out.println("i : " + i + ", j: " + j + " &  matches: " + matches);
					
					if(matches > mostMatches){
						mostMatches = matches;
					}
				}
				
				
			}
		}
		
		
		
		
		/*
		
		while(i < str1.length()){
			if(j < str2.length()){
				for(int k = j; k < str2.length(); k++){
					
					
					while(str1.charAt(i) == str2.charAt(k)){
						
					}
				}
				if(str1.charAt(i) == str2.charAt(j)){
					matches++;
				}
			}
			i++;
		}
		
		
		
		for(int i = 0; i < str1.length(); i++){
			for(int j = 0; j < str2.length(); j++){
				if(str1.charAt(i) == str2.charAt(j)){
					int matches = 1;
					for(int k = i; k < str1.length(); k++){
						for(int l = j; l < str2.length(); l++){
							if(str1.charAt(k) == str2.charAt(l)){
								matches++;
							}
						}
					}
					if(matches > mostMatches){
						mostMatches = matches;
					}
				}
			}
		}
		*/
		
		System.out.println("Most matches: " + mostMatches);
		return mostMatches;

	}
	
	public static void main(String[] args){
		longComSubSeq("AZBBACXCABACC", "CBBACCCAABBCXYZ");
	}
	
	
	

}

:l Looks like a lot of Villavu members don't know what recursion is.. It's nice to try to help but you need to understand the problem first and what recursion is.

As for the second assignment.. Meh I'm lazy but if it's not solved still I'll write something up.

Recursion is when a function calls itself and keeps pushing to the stack. When the stack unwinds, it calls the function in the reverse order of the order it was called in.. If the stack is pushed too much and never pops/unwinds then we have a stack-overflow. For every push, there should be a pop. A pop is a function call in the reverse order of which it was called.

First in last out is the rule. It's like a bookstack. You add books on top of books but never pull from the bottom. Take a book off the top and that's how the stack unwinds.

I should also mention that if you add too many things to the stack at once, it will overflow as well regardless of the return statement for breaking. Example would be the letter P. I've tried entering up to O and it worked fine. After letter P-Z will overflow or cause undefined behaviour. Heap allocations can ease the stack but there's also something called a heap overflow. I won't get into all that. But my warning is: watch out with recursion. Also objects have a maximum of 2GB in size in some languages such as C#. I'm not sure for java but that could also be a problem when using the += operator.

package recursive;

public class Recursion
{
    int J = 'A';
    String Pattern = "";
            
    public void printLetterPattern(char C, String Old)
    {         
        Pattern += 'A';
        if (C - 'A' == 0) return;  //This decides when to unwind/pop values off.
        Pattern += (char)(++J);
        Pattern += Old;
        printLetterPattern((char)(C - 1), Pattern);
    }
    
    public String Get()
    {
        return Pattern;
    }
}




package recursive;

public class Recursive
{
    public static void main(String[] args)
    {
        Recursion F = new Recursion();
        F.printLetterPattern('D', "");
        System.out.println(F.Get());
    }
}

Thank you do muh everyone who has posted, I will try to figure everything you all posted when I get back to my dorm. Argh java

This should do nicely for Q1

import java.util.*;
import java.lang.*;

class Main
{
    static boolean invert = false;
    public static void sillyhomework(char c) {
        int i = -1; 
        if (c == 'A') 
        System.out.print('A');
        else {
            if (invert) i = 0;
            
    
            System.out.print( "ABA" + (char)(c + i));
            invert = !invert;
            
        }
        
        if (!invert) {
            System.out.print( "ABA" + (char)(--c) +  "ABA");
            return;
        }
        sillyhomework(c);
    }
    
    public static void main (String[] args) throws java.lang.Exception
    {
        sillyhomework('D');
    }
}

Nobody here really seems to have nailed the first problem, which is strange because it has a really straightforward solution if you read through the problem description.

The basic goal of using recursion is to continuously reduce the problem over and over (this is the recursive part) until you find a problem so easy (called the base case) that you can solve it right away. Then, you can combine the result of that problem with the next more complicated problem to get that answer, and so on until you end up solving the original problem.

When you're trying to solve a recursive problem, you need to identify two things: the base case(s) and the recursive case(s). If we look through the problem description for our problem, we can see that the base case occurs if c is equal to 'A'. If that happens, we know to just print out 'A' and return from the method. That appears to be the only such case, so we can conclude that the rest of the algorithm is our recursive case. Indeed, we can see that the first and last open bullet points reference the output for the previous character, so we know that we'll probably have to use recursion for those parts.

The basic structure of the code for a recursive problem will look like this:

function f(x) {
  if (base case condition {
    // handle base case(s)
  } else {
    // handle recursive case(s)
  }
}

In our case, we're given some information about the method we have to write, so we can start to structure our code:

public static void printLetterPattern(char c) {
  if (base case condition) {
    // handle base case
  } else {
    // handle recursive case
  }
}

The base case should be pretty easy to do, so we'll focus on the recursive part. The instructions say we should do the following, in order:

1. Print the pattern for the previous letter.
2. Print out the current letter.
3. Print the pattern for the previous letter again.

Number 2 seems easy enough, but how about numbers 1 and 3? How do we print the pattern for the previous letter? Do we have a function to do this? I claim that we do, and that it's the very same function that we're writing! As a result, we can simply call it with the "previous letter" as an argument and have it do all of the work of printing out the pattern for us!

If it helps, here is a picture of the function that we are defining. I've renamed it to f in order to save space. Note that the + operation is for string concatenation, not addition. What's nice about writing it this way is that we've expressed our function's behavior very succinctly and elegantly. That's often the case with recursive functions – their behavior can be described easily and subsequent implementations are often simpler than those using iteration.


Anyway, I won't post the final code (which should really only be ~7 lines long), since I don't want to solve the problem for you completely, but I hope this helps.

Nobody here really seems to have nailed the first problem

What? Completely ignored my post :S

Slushpuppy that isn't recursive. That function never calls itself.

From: Brandon
What? Completely ignored my post :S

Slushpuppy that isn't recursive. That function never calls itself.

you may want to take a look at it again

From: Brandon
What? Completely ignored my post :S

I read through every post in this thread, including yours, and your solution doesn't demonstrate a good understanding of the problem. What you've posted hacks around the problem instead of using recursion well, and it also requires extra internal state that isn't necessary.

The solution is actually quite simple and straightforward if you read through and understand the problem description.

From: Method
I read through every post in this thread, including yours, and your solution doesn't demonstrate a good understanding of the problem. What you've posted hacks around the problem instead of using recursion well, and it also requires extra internal state that isn't necessary.

The solution is actually quite simple and straightforward if you read through and understand the problem description.

Not so straight forward..


I'd say yours is just as hacky. Still throws a stack overflow. According to your formula it should be (that is if I read it right):

    public void printLetterPattern(char C)
    {
        if (C == 'A')
        {
            System.out.print('A');
        }
        else
        {
            printLetterPattern((char)(C - 1));
            System.out.print(C);
            printLetterPattern((char)(C - 1));
        }
    }

Same stackoverflow, same amount of letters. Except, yours prints so much it lags way more than mines.. Guess there is no straightforward way to do "all" the letters of the alphabet.

From: Brandon
Not so straight forward..


I'd say yours is just as hacky. Still throws a stack overflow. According to your formula it should be (that is if I read it right):

    public void printLetterPattern(char C)
    {
        if (C == 'A')
        {
            System.out.print('A');
        }
        else
        {
            printLetterPattern((char)(C - 1));
            System.out.print(C);
            printLetterPattern((char)(C - 1));
        }
    }

Same stackoverflow, same amount of letters. Except, yours prints so much it lags way more than mines.. Guess there is no straightforward way to do "all" the letters of the alphabet.

Could you explain why you think that that solution is "hacky"?

If you're getting a stack overflow, you probably don't have enough stack space for the 26 or so stack frames it would take for the call to printLetterPattern('Z'). I get no such exception when running the code you've posted. I'd imagine trying to print out over 67 million characters is contributing to the lag you're experiencing as well.

Also, the formula in my post is simply a mathematical representation of the algorithm given in the problem description.