How to Approche
When we hear a problem beginning with: ‘Write a method to compute all…’, it is often a good candidate for recursion. By definition recursive solutions are built of solving subproblems. Simply speaking when we need to compute f(n)
, we need first to solve a problem for f(n1)
, to solve the problem for f(n1)
we need to do the same for f(n2)
and so on. Always at the end we need to face so called ‘base case’  f(0)
or f(1)
, which is the most easiest subproblem. Good news is that for this problem we know a solution and many times it is just a hard coded value.
Problem
Our task is to write a function List<String>perm(String str)
which will return all permutations of a string given in the argument. To proceed let’s think how this problem can be splitted into smaller subproblems and how to connect those problems in the recursive way.
To find a pattern we will write all permutations of following strings 'a'
, 'b'
, 'c'
, 'ab'
, 'ac'
, 'bc'
, 'abc'
1 2 3 4 5 6 7 

If You have some experience in solving such puzzles You probably noticed a following pattern
1 2 3 4 5 6 7 

where 
means a concatenation of two strings.
First three cases are called ‘base cases’ and as I mentioned before they can be easily solved. A permutation of a string containing one character is just the same string. At this point of analysis we can now try to write a small program which will solve our problem.
Coding
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 

1 2 3 4 5 6 7 8 

1 2 3 4 5 6 7 
