I am trying to learn Java, and now I'm trying algorithms. So, I'm stucked on recursion. I have a code that I don't understand.

public static String reverseString(String text){
  
// base case
  
if (text.length() == 0) {
    return text;
  } 

else {

    // recursive call

    return reverseString(text.substring(1))   text.charAt(0);
  }
}
 
public static void main(String[] args) {
  String str = new String("howdy");
  // calling recursive function
  String reverse = reverseString(str);
  System.out.println(reverse); // Prints: ydwoh
}

Problem is that for me recursive call in this code for me is:

for the first time it retuns owdyh,

second time wdyo and so on.

I can't understand how the string ydwoh borns. I suspect that somewhere chars concotanating in the right order, and stored somewhere, but where is this place I also don't know.

UPDATE

I tried it with paper, what I got:

first recursive call:

return value owdyh = "owdy" "h"

second call:

return value wdyo = "wdy" "o"

and so on

CodePudding user response：

The difficulty is the processing after the call. The first letter is added to the end of the result of reverseString of the rest.

reverseString "howdy"
  reverseString "owdy"
    reverseString "wdy"
      reverseString "dy"
        reverseString "y"
          reverseString ""
            return ""
          return ""   "y"
        returns "y"   "d"
      returns "yd"   "w"
    returns "ydw"   "o"
  returns "ydwo"   "h"
returns "ydwoh"

It is like a mathematical proof by induction:

• The empty string is reversed (result empty string).
• When the recursive call works on a smaller string, placing the first char at the end, also reverses the string.
• So reverseString works for all length of strings.

CodePudding user response：

Thanks for the answers! They helped me to figure out my misunderstanding! What I couldn't understand is where all the chars from the text.charAt(0) are stored! The trick is that they are stored in the stack without any links. It's LIFO(Last-In-First-Out) approach in work.