Using recursion to do permutations

Solving problems using recursion.
 I have always had problems in understanding deep and complex recusion eventhough they all follow a common pattern that  is There is always a base case to stop the recursion and making a recursive call on some smaller part of the solution, I decided to set my bar high . Here are the things i set to use recursion to understand complex recursive calls .

1. Solving Sudoku using Backtracking
2. The Chess  Knight - Queen classic
3. Permutations
4. More problems as I come across.

Let start with the case that allows you to select all possible combinations of all members a set. I learnt that this recursive pattern in very important to understand because the is a common pattern used in solving the problems that I mentioned above and many others like searching and solving word puzzles
  Permutation
  I define  permutations as all the ways to arrange a set of items for example if you permute the word {cat} you get {cat, tac, act, atc, tca, cta}. Permutations are mathematical and if you want a deeper understanding of this then go to Permutation. in Wikepidia and read more
In the program below  the program does  permutation recursively . I am writing this because I feel I have started getting the power of recursion and how to solve problems with them. The truth is i understood the classical recursive  examples in the university like  Fibonacci ,factorials and the towers of Hanoi  but when it came to complex recursive example like the one below. I got a headache in thinking recursively.
 Here are the tough questions to answer when writing a program that does permutations.

1. How do you just pick one element on the set and know which one to attach next? 
2. How do you avoid doubles and repeating each elements?
3. How do you separate them? 
4. How do you know that all the possible combinations of the set have been made?

Here is the program written in C# that does permutations .

class Program
    {
        static void Main(string[] args)
        {
            Permutate("ABCD");
        }
        public static void RecPermute(string permutateHolder , string itemToPermutate)
        {
            if (itemToPermutate== string.Empty)
            {
                Console.WriteLine(permutateHolder);
            }
            else
            {
                for (int i = 0; i < itemToPermutate.Length; i++)
                {   // Get the rest of the items remaining in the set
                    var remaining = itemToPermutate.Substring(0, i) + itemToPermutate.Substring(i+1);
               //Take each element from the item and do a recursive call on them
                    RecPermute(permutateHolder + itemToPermutate[i], remaining);                    
                }
            }
        }

        // Wrapper for permutate function
        public static void Permutate(string item)
        {
            RecPermute("", item);
        }
    }

Here is part of the recursive tree of the program Permutate("ABCD").It show permutations for all elements beginning with the letter A.The other elements of the set follow the same pattern.

Happy programming !