understanding the difference Between string permutation Recursive cases

Question

   class RecursionExample
       {
           private static void doPermute(String str, int l, int r)
            {
                if (l == r)
                    Console.WriteLine(str);
                else
                {
                    for (int i = l; i <= r; i++)
                    {
                        str = swap(str, l, i);
                        doPermute(str, l + 1, r);
                        str = swap(str, l, i);
                    }
                }
            }

            public static String swap(String a,int i, int j)
            {
                char temp;
                char[] charArray = a.ToCharArray();
                temp = charArray[i];
                charArray[i] = charArray[j];
                charArray[j] = temp;
                string s = new string(charArray);
                return s;
            }

            public static void Main()
            {
                String str = "ABC";
                int n = str.Length;
                doPermute(str, 0, n - 1);
            }
     }

Compared to

class RecursionExample
    {
        private static void doPermute(String str, int l, int r)
        {
            if (l == r)
                Console.WriteLine(str);
            else
            {
                for (int i = l; i <= r; i++)
                {
                    str = swap(str, l, i);
                    doPermute(str, l + 1, r);
                }
            }
        }

        public static String swap(String a,int i, int j)
        {
            char temp;
            char[] charArray = a.ToCharArray();
            temp = charArray[i];
            charArray[i] = charArray[j];
            charArray[j] = temp;
            string s = new string(charArray);
            return s;
        }

        public static void Main()
        {
            String str = "ABC";
            int n = str.Length;
            doPermute(str, 0, n - 1);
        }
 }

Both print out the exact same thing, the difference is the first one calls the swap method after the permute recursive call. from what I read online the bottom swap is to "backtrack" back to the previous case, but it can back track just fine without having to do that extra swap? could someone explain what I am missing or not understanding? for me the bottom one makes more sense to me.

Answer 1

So I just wasted 5 minutes researching permutation algorithms...

Back tracking is only useful when you are working with direct memory or references. Since strings are immutable in C#, the change doesn't get pushed back through the recursive stack, so the back tracking isn't useful for returning the state back to its previous pre-recursed state (in essence nothing gets changed anyway).

However, if you to use ref (or an array or something of that ilk) you would not only find your input being mutated, worse still you would receive the wrong result.

Example

private static void doPermute(ref string str, int l, int r)
{
   if (l == r)
      Console.WriteLine(str);
   else
   {
      for (int i = l; i <= r; i++)
      {
         str = swap(str, l, i);
         doPermute(ref str, l + 1, r);
         str = swap(str, l, i);

      }
   }
}

Output with backtracking

ABC
ACB
BAC
BCA
CBA
CAB

Output without backtracking

ABC
ACB
CAB
CBA
ABC
ACB

In summary, it serves no purposes if you are not using direct memory or references.