CODEWITHSUNDEEP
javarecursion
crazymind
crazymind

Reputation: 169

calling stack of reversing a string use recursion

I have a trouble of understanding the calling stack of reverse a string use follow code:

public static String reverseString(String str) {
        String reverse = "";
        if (str.length() == 1) {

            return str; 
        } else {
            reverse += str.charAt(str.length() - 1) + reverseString(str.substring(0, str.length() - 1));
            return reverse;
        }
    }

You can see the stack build up from 1 to 4 and then pop from 4 to 1. Take str = "abcd" as an example. It should returns "a" first (since "a" pop from calling stack firstly) which does not reverse a string. Am I getting something wrong here? thanks!

enter image description here

Upvotes: 0

Views: 308

Answers (2)

Susheel Dwivedi
Susheel Dwivedi

Reputation: 94

Your program work fine But you unable trace your program. Below i show stack frame of all recursive call in your program(both stack up and stack down). stacktraceimage

Upvotes: 1

Shariq
Shariq

Reputation: 506

Consider carefully the following block in the code: 

else {
        reverse += str.charAt(str.length() - 1) + reverseString(str.substring(0, str.length() - 1));
        return reverse;
    }

The calling stack, is recursing the function with the last character excluded, and the excluded character is appended to the variable reverse. What you're missing in your understanding is, first the call stack is returning the last excluded character, which is 'd', not 'a' as you mentioned, and appending it to string 'reverse'.

Reiterating the code manually:
reverse       input //reverseString(input)
1. d        abcd
2. c       abc
3. b       ab
4. a       a //return a as length is 1, the if block

You can see the reverse string building up with each call.

Upvotes: 1

Related Questions