Recursion

[dense anvil]

I am having trouble understanding how to do Recursion when it comes to String

[noble siren]

⌛ This post has been reserved for your question.

Hey @dense anvil! Please use /close or the Close Post button above when you're finished. Please remember to follow the help guidelines. This post will be automatically closed after 300 minutes of inactivity.

TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.

[dense anvil]

I have a good chunk of the code done

Ill post it here

import java.util.Scanner;
public class Exercise{
    //this will act as the main recursive method for reversing a string
    public static String reverse(String str){
        { //Base or stop condition
            return str;}
            else{
                return str + str.charAt(0);//recursive call 
            }
    }
    public static void main (String[] args){
        Scanner reader = new Scanner(System.in);
        String str= "This is an example";
        System.out.println(reverse(str));
    }
}

[jade sandal]

your method is missing a recursive call to itself i think

[copper frost]

And a base case, and a reduction/evolution of the case

I guess first OP should discuss about what they think the base case is supposed to be

[dense anvil]

Thats how it was setup from the previous exercises/examples we did yesterday (for context the class is just a intro cor Computer science) as we were just getting started with recursive.
I just have no idea how to go about making a string into a base condition/stop condition

[copper frost]

But concerning general ideas, do you have general ideas?

[dense anvil]

I have some

also found a example

just had to transfer it into javav, give me a moment

int factorial(int n){
    if(n == 0){//base condition
        return 1;
    } else {
        return n * factorial(n-1); //recursive call
    }
}
void main(String[] args){
    int n; //
    System.out.println("Enter the number: ");
    n= reader.nextInt(); // we assume the user enter a positive number
    System.out.println("The factorial for “+ n+ “ is “+ factorial(n));
}

[copper frost]

Yes, that's the typical example for recursion

And indeed, it's not on Strings that it operates

But do you understand it?

[dense anvil]

a little bit
I am having trouble getting the idea of how it would be done with a string

I understand the factorial for this

[copper frost]

The idea is incrementally reducing the problem, until you get one where the response is trivial.

Can you imagine a String about which it is trivial to reverse it?

[dense anvil]

Hmm I can

[copper frost]

excellent. When you feel you've fantasized enough about it in your head, please share it here

[dense anvil]

Okay

Alright

I think I got it

atleast for the base case

if(str == "")

not sure about the recursive call

[copper frost]

Well now you need to find a way to take in any String, and gradually turn it into your base case

Here your base case is the empty string

Can you think of a way to, one step at a time, modify a string so that it ends up being the empty string?

[dense anvil]

not at the moment

Also if it helps I can show you what the exercise im doing (the current work im having trouble with) is as we are just filling in the blank

[copper frost]

I have a confession to make to you: I know how to reverse a String recursively

I'm merely, at your request, trying to guide you into doing it too

[dense anvil]

Ah gotcha

[copper frost]

But I suppose you can show the exercise anyway

[dense anvil]

yeah, I feel i phrased it in a way that its a full on working program

[copper frost]

Ah, they force on you to append the first char to the result of the recursive call

[dense anvil]

yeah

[copper frost]

It sounds like that force us to deal with this first character when we reduce the string

do you think we can get the trick by turning it uppercase?

[dense anvil]

hmm no I dont believe so unless im over looking something

[copper frost]

AH, you're right, turning it uppercase doesn't reduce the case

Maybe we could double the first char, like, turning "Hello" into "HHello"?

[dense anvil]

hmm that can work

[copper frost]

Yeah? Maybe eventually the string will be an empty string

Let's try it

Hello

HHello

HHHello

HHHHello

I wonder when will it be the empty string

[dense anvil]

hmm I feel i am mis interpeting something

give me a second

hmm that wasn't really helpful
I looked over the material and it aint that helpful

[copper frost]

That's great, but we were in the middle of a conversation here

[dense anvil]

Apologies

[copper frost]

So, what do you think about the idea to double the first character to reduce the case?

[dense anvil]

It can work with reducing the case but it feels like it would end up being like a loop

[copper frost]

Really, you have the impression that this, is increasingly reducing the case?
Hello
HHello
HHHello
HHHHello

[dense anvil]

No
Now that I think about it

it will just keep adding onto the case instead of reducing it

[copper frost]

Ah, right

So, what could we do to this first character...

Tried turning it uppercase, doesn't really help

Tried doubling it, doesn't really help

What else, what else...

Maybe we could swap it with the next character?

[dense anvil]

hmm maybe

[copper frost]

Let's try that, Like when I tried doubling it on the example "Hello"

Can you show here what it does?

[dense anvil]

I can give it a try

[deep zodiac]

Hello people, can I join in to help?

[dense anvil]

uh sure?

[deep zodiac]

So you're trying to reverse a string, correct?

recursively

[dense anvil]

Correct

[deep zodiac]

mhm now what are some important things in a recursive function

There are 2 main components

One is the base case

[dense anvil]

the base and the recursive call

[deep zodiac]

lovely!

[dense anvil]

just don't know how to do that for a string

[deep zodiac]

now let's look at the function "public static String reverse"

[dense anvil]

doesnt help all of our examples are of factorials

[deep zodiac]

if you're reversing a string

would you need to reduce the string

as the function goes on

Like my first call of "Hello" would be
elloH and then
lloHe

right? if you're trying to reverse it

[dense anvil]

Right

[deep zodiac]

mhm so in the recursive calls, you would need to reduce the string length as you're passing it

and the base would check when the str.length() == 1, then you stop the recursive function

Let's think of it this way:

The code says ____ + str.chatAt(0)
If I say "Hello", it will say "HelloH"

this would be the case for reverse(str) + str.chatAt(0)

but now, if I say reverse(str.subString(1)) + str.charAt(0)

What do you think is the output (assuming it runs one time)

[dense anvil]

it would be HHeello

I think

[deep zodiac]

Hm? Why? Isn't the str.chatAt(0) after the string?

what will be the output of str.subString(1)

assuming you say String h = str.subString(1);
System.out.println(h);

Don't worry it's just a simple question, like general question of what will the value be

[dense anvil]

this feels like its such a obvious answer but my mind is failing me with it

[deep zodiac]

How does the subString function with one param work? It starts from that index right?

[dense anvil]

Right

[deep zodiac]

So "Hello" would be ?

[dense anvil]

ello

[deep zodiac]

Awesome!

now Let's say str.subString(1) + str.charAt(0)

[dense anvil]

it would be Elloh

[deep zodiac]

Careful, it would be elloH but you know the idea!

Now, here's the tough part:

what if I make it do this again and again

reverse(str.subString(1)) + str.charAt(0)

the INITIAL reverse function will have

"ello" + "H"

but if I put "ello" in the reverse function

what happens?

if I say reverse("ello")
will it be `"llo + e"?

[dense anvil]

it would print it out as
"llo" + "e"

[deep zodiac]

oooo see you're getting the hang of it

now now now, let's say you're at the last case

which is o + str.charAt(0)

but we know that str.charAt(0) IS o

so your string would become oolleH

Which is wrong, meaning the "base case" shouldn't return the last string left

You get what I'm saying?

[dense anvil]

yeah

[deep zodiac]

What do you think should the base case be

[dense anvil]

hmm i wanna say
(str == str.subString(1))

[deep zodiac]

It has something to do with str's length

that's true

but maybe think about when the function should end

maybe when there's no characters left in str?

[dense anvil]

yeah, as that would make sense so hmm
I wanna say str.length() == 1 since if it keeps repeating we will eventually.. nvm
we would just be left with the (0)

[deep zodiac]

I would use <= 1 but yeah, that looks right!

[dense anvil]

Man this is way better than having to scour the internet for examples to even get a idea on it

[deep zodiac]

so basically it's if(str.length() == 1){}

[deep zodiac]

Lol recursion is tough

anyways, so assuming if we know the base case is when there's no length left in str

[dense anvil]

yeah and I feel string is more difficult
mainly because all i find is factorial recursion

[deep zodiac]

how should we continue with the recursive calls?

[deep zodiac]

factorial isn't easy either tho

[dense anvil]

Aye but it has alot of explanation on it from what I came across
also hmm I wanna say by doing like we talked about earlier

[deep zodiac]

ig

[dense anvil]

so like by doing something like return(str.subString(1)) + str.charAt(0)

[deep zodiac]

hm...

actually I think it should be str.subString(0, str.length()-1)

(I'm changing ways a little)

and you add the last character

[dense anvil]

thats fine! also sounds interesting with adding the last character

[deep zodiac]

damn I'm so tired rn

wait let me think this through

how to explain

ok so here's the idea:

if we add the last character, let's say it's "Hello"
then we have Hell + o
Hel + ol
He + oll
H + olle

• olleH

you see what I mean?

the base case is still the same though

[dense anvil]

that makes sense

[deep zodiac]

you're just going to pass in reverse(str.subString(0, str.length()-1)) + str.charAt(str.length()-1);

cuz you're shortening the string input as it goes and just plucking the last char and making it first into the string

I'm working through it as we speak, and it works like intended

[dense anvil]

i am trying to think of what else to say instead of "That makes sense"

because I feel like I said that so many times

[deep zodiac]

lol it's ok

[dense anvil]

but thank you for helping me understand recursion

[noble siren]

If you are finished with your post, please close it.
If you are not, please ignore this message.
Note that you will not be able to send further messages here after this post have been closed but you will be able to create new posts.

[dense anvil]

this has been extremely helpful

[deep zodiac]

wait

wait a min!

[dense anvil]

what is it?

[deep zodiac]

aha, woops I meant str.charAt(str.length()-1) + reverse(str.subString(0, str.length()-1))

cuz you're adding it first not last 💀

or else that's just returning the original string lmao

[dense anvil]

lmao that fine!

[deep zodiac]

awesome! glad to be of help

also I reccomend a course in recursion

https://www.youtube.com/watch?v=IJDJ0kBx2LM

This was very useful for me! (you can choose to ignore it)

[dense anvil]

Thank you!
I will make sre to watch this

[deep zodiac]

and in order to continue your coding practice

https://codingbat.com/java

here's codingbat, you can choose "recursion" to do recursive problems

It's awesome for getting that coding spirt~

like this lol

[dense anvil]

that is going to be extremely helpful

now I just need to do some quick tracing of the code by merely writting it out and ill be done