× {{alert.msg}} Never ask again
Get notified about new tutorials RECEIVE NEW TUTORIALS

how java uses recursion to reverse a string

Xaver Kapeller
Mar 13, 2015
<h2>Detailed explanation:</h2> <p>First you start with this String: </p> <pre><code>"123456" </code></pre> <p>And it first reaches this condition:</p> <pre><code>if (str.length() &lt; 2) { return str; } </code></pre> <p>The <code>String</code> is longer than 1 character so it does nothing here. The next executed method is this:</p> <pre><code>System.out.println(str.substring(1) + " "+ str.charAt(0)); </code></pre> <p>For simplicity we are just looking at the inner part:</p> <pre><code>str.substring(1) + " " + str.charAt(0) </code></pre> <p>So here are two method <code>substring(int)</code> and <code>charAt(int)</code>. </p> <ol> <li><code>substring(int)</code>: This method returns as the name implies a substring of the original string. It starts at the index you pass into the method.</li> <li><code>charAt(int)</code>: This returns the character at the given position in the <code>String</code>.</li> </ol> <p>So now if we again look at the code in the method, remember currently str is "123456".</p> <p>If we use <code>substring(1)</code> on this <code>String</code> it will return everything beginning at index 1, so <code>substring(1)</code> returns "23456". Just the first character is left out.</p> <p>If we use <code>charAt(0)</code> we get the first character in the <code>String</code>m so <code>charAt(0)</code> returns just "1".</p> <p>So now we know what values are returned by those methods in the first iteration:</p> <pre><code>str.substring(1) + " " + str.charAt(0) = "23456 1" | | V V "23456" + " " + "1" = "23456 1" </code></pre> <p>And after that the recursion starts:</p> <pre><code>return reverseRecursively(str.substring(1)) + str.charAt(0); </code></pre> <p>So the value of <code>str.substring(1)</code> is now passed into <code>reverseRecursively()</code>. The <code>str.charAt(0)</code> here is just appended to the <code>String</code> once <code>reverseRecursively()</code> returns. In other words it looks like this:</p> <pre><code>return reverseRecursively("23456") + "1"; </code></pre> <p>In the next iteration everything starts over, the only difference is that now <code>reverseRecursively()</code> starts with the <code>String</code> "23456" instead of "123456". So in the end it would come down to this:</p> <pre><code>return reverseRecursively("3456") + "2" + "1"; </code></pre> <p>Again in the next iteration it would work out to this:</p> <pre><code>return reverseRecursively("456") + "3" + "2" + "1"; </code></pre> <p>And this goes on and on until the <code>String</code> passed into <code>reverseRecursively()</code> has a length smaller than two, so once the recursion reaches this:</p> <pre><code>reverseRecursively("6") </code></pre> <p>The if statement will kick in and just return the <code>String</code> <code>"6"</code>.</p> <pre><code>if (str.length() &lt; 2) { return str; } </code></pre> <p>So in the end the result will be this:</p> <pre><code>"6" + "5" + "4" + "3" + "2" + "1" = "654321" </code></pre> <hr> <h2>Summary</h2> <blockquote> <p><strong>So to summarise:</strong> </p> <p>What this method does is take everything from the <code>String</code> but the first character and the first character is added to the end of the <code>String</code> after passing the rest of the <code>String</code> again into <code>reverseRecursively()</code> again causing the first character to be appended to the end and everything else starts over. The whole thing stops once the <code>String</code> reaches a length of 1.</p> </blockquote> <p>So what this all boils down to is this:</p> <pre><code> "123456" "23456" + "1" "3456" + "2" + "1" "456" + "3" + "2" + "1" "56" + "4" + "3" + "2" + "1" "6" + "5" + "4" + "3" + "2" + "1" = "654321" </code></pre> <p>I hope I could explain the algorithm properly! If you have any further questions please feel free to ask!</p> <p>This tip was originally posted on <a href="http://stackoverflow.com/questions/24827824/how%20java%20uses%20recursion%20to%20reverse%20a%20string/24828273">Stack Overflow</a>.</p>
comments powered by Disqus