title: String permutations using recursion in Java
body: <p>I came across <a href="http://learnprogramming.machinesentience.com/java_permutations_recursion/" rel="noreferrer">THIS</a> post which tried very hard to explain the recursive solution to print all string.</p>
  <pre class="lang-java prettyprint-override"><code>public class Main {
      private static void permutation(String prefix, String str) {
          int n = str.length();
          if (n == 0)
              System.out.println(prefix);
          else {
              for (int i = 0; i &lt; n; i++)
                  permutation(prefix + str.charAt(i),
                          str.substring(0, i) + str.substring(i + 1));
          }
      }
  
      public static void main(String[] args) {
          permutation(&quot;&quot;, &quot;ABCD&quot;);
      }
  }
  </code></pre>
  <p>But still I am not able to get the part when we start popping off the stack. For example, recursion goes all the way till <code>permutation(&quot;ABCD&quot;,&quot;&quot;)</code>, where base case meets and it prints <code>ABCD</code>. But what happens now? We pop off <code>permutation(&quot;ABC&quot;,&quot;D&quot;)</code> from function call stack. What we do with this and so on?</p>
  <p>Can someone please help explain a bit?</p>
  <p>Also, I need some pointers on the time complexity of this. Not like complete calculation but some hints.</p>