String return value in recursive function in java

Question

So I'm practicing java currently, I'm a beginner and I try to explain all the examples that I code so I can understand how and why things are like that. I understand the concept of recursion but I came across this problem when I tried to explain this code:

import java.util.Scanner;
public class JavaExample {

    public static void main(String[] args) {
        String str;
        System.out.println("Enter your username: ");
        Scanner scanner = new Scanner(System.in);
        str = scanner.nextLine();
        scanner.close();
        String reversed = reverseString(str);
        System.out.println("The reversed string is: " + reversed);
    }

    public static String reverseString(String str)
    {
        if (str.isEmpty())
            return str;
        //Calling Function Recursively
        return reverseString(str.substring(1)) + str.charAt(0);
    }
}

With my knowledge so far about recursion, I tried to explain it like this. Let's have for example a string "Petar":

reverseString(etar)+P
reverseString((tar)+etar)+P
reverseString((ar)+tar+etar)+P
reverseString((r)+ar+tar+etar)+P
-----------------------------------
r+ar+tar+etar+P

I noticed that the right answer is the first character from every individual piece, so I must be close.

Thank you for your time and I'm sorry if I didn't express myself clearly, I'm from Europe (sry bad inglish).

azro · Accepted Answer · 2020-06-06 12:01:55Z

1

You doing good for first line reverseString(etar)+P you keep at the end only the *first char**, just do the same for next lines

put first char at the end
send the rest to the method

reverseString(etar)+P
reverseString(tar) +e+P
reverseString(ar)  +t+e+P
reverseString(r)   +a+t+e+P
reverseString('')  +r+a+t+e+P // stops when empty string is passed

answered Jun 6, 2020 at 12:01

azro

54.2k9 gold badges38 silver badges75 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Petar Brdaroski Over a year ago

I thought it was like: (reverseString(str.substring(1))) + str.charAt(0), aka I thought that the method was calling only for the str.substring(1). But thank for the answer it helped a lot!

Netanel · Accepted Answer · 2020-06-06 12:02:17Z

1

You got the first call right but the others were a bit off. In each recursive call you return the the string with the first character at the end instead of the begining. Thus, the recursion looks something like this:

reverseString("Petar")
return reverseString("etar") + "P"
return reverseString("tar") + "e"
return reverseString("ar") + "t"
return reverseString("r") + "a"
return reverseString("") + "r"
return ""

So the function will return: (((((("")+"r")+"a")+"t")+"e")+"P"), which is "rateP".

answered Jun 6, 2020 at 12:02

Netanel

4873 silver badges11 bronze badges

1 Comment

Petar Brdaroski Over a year ago

Thank you very much for the explanation, I appreciate the time!

knittl · Accepted Answer · 2020-06-06 12:10:49Z

1

It should become clear when start with the simplest possible example: the empty string and string of size 1. Then substituting arguments of each call, to make it more obvious:

// string.isEmpty() is true, so the empty string is returned immediately
reverse("")  -> "" 
reverse("a") -> reverse("") + 'a' -> ("") + 'a' -> "a"

These are the trivial examples, let's try it with longer strings:

reverse("ab")  -> reverse("b") + 'a'
reverse("abc") -> reverse("bc") + 'a'
               -> (reverse("c") + 'b') + 'a'
               -> ((reverse("") + 'c') + 'b') + 'a'
               -> ((("") + 'c') + 'b') + 'a'
               -> "cba"

The general pattern should be clear now. For the sake of completeness, let's manually "unroll" the recursive calls for a 4 character string:

reverse("abcd") -> reverse("bcd") + 'a'
                -> (reverse("cd") + 'b') + 'a'
                -> ((reverse("d") + 'c') + 'b') + 'a'
                -> (((reverse("") + 'd') + 'c') + 'b') + 'a'
                -> (((("") + 'd') + 'c') + 'b') + 'a'
                -> "dcba"

edited Jun 6, 2020 at 12:10

answered Jun 6, 2020 at 12:02

knittl

269k59 gold badges339 silver badges405 bronze badges

2 Comments

Petar Brdaroski Over a year ago

Oh, it's clear now. I was wrong because I thought that the method was self calling only with the str.substring(1) portion, aka (reverseString(str.substring(1))) + str.charAt(0). Thank you very much for your answer!

knittl Over a year ago

@PetarBrdaroski it is. The recursive call is only passed the "tail" of the string. The head is appended after the recursive call returns

Arvind Kumar Avinash · Accepted Answer · 2020-06-06 15:01:33Z

0

It works like this:

reverseString("Peter") = 
        reverseString("eter") + P = 
                (reverseString("ter") + e) + P = 
                    ((reverseString("er") + t) + e) + P = 
                        (((reverseString("r") + e) + t) + e) + P = 
                            ((((reverseString("") + r) + e) + t) + e) + P =
                            (((("" + r) + e) + t) + e) + P =
                            ((((r) + e) + t) + e) + P =
                            (((r + e) + t) + e) + P = 
                            (((re) + t) + e) + P = 
                            ((re + t) + e) + P = 
                            ((ret) + e) + P = 
                            (ret + e) + P = 
                            (rete) + P = 
                            rete + P = 
                            reteP

edited Jun 6, 2020 at 15:01

answered Jun 6, 2020 at 12:35

Arvind Kumar Avinash

81k10 gold badges98 silver badges144 bronze badges

1 Comment

Petar Brdaroski Over a year ago

Thank you so much for the broken down answer. Really appreciate the time and effort. It's all clear now!

Ahmed Sayed Mansour · Accepted Answer · 2020-06-06 12:03:08Z

0

On your example when your function reaches only one character like Peter when it becomes only "P" and the string is not empty you call

substring(1)

Which calls an index out of the range while the string only have P on index 0 and none on index 1 You have to put a base case that checks if the string length is equal to 1 or less

answered Jun 6, 2020 at 12:03

Ahmed Sayed Mansour

195 bronze badges

Collectives™ on Stack Overflow

String return value in recursive function in java

5 Answers 5

1 Comment

1 Comment

2 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

1 Comment

2 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related