I don't seem to grasp the concept of recursion. Any help is much appreciated.

There are two parts to any recursive algorithm. The first part is that the algorithm should do part of the work, which results in nearly the same problem, but closer to the solution. For example, you do the 1st character of the string permutation, but you depend on the algorithm to do the rest.

The second part is the end game. There comes a point where the problem is so easy that the recursive algorith is not needed anymore. For example, if there is only 1 letter left, then the result is simply a single output line.

You have done the first part. Now how do you determine when you are done?

I am afraid, not only is such a reply to a year-old post of little use, but also it does nobody any good to be given a straight answer like that. Please look at this FAQ too. Look what it says at the top of the beginners' contents page:

We're all here to learn, so when responding to others, please focus on helping them discover their own solutions, instead of simply providing answers.

I have reluctantly felt obliged to move your solution to our "deleted" forum.