Search code examples
algorithmrecursiondata-structurespermutationtail-recursion

What is the algorithm of thinking recursive? (on the specific example)

I just can't wrap my head around recursion. I understand all of the concepts (breaking solution into smaller cases) and I can understand solutions after I read them over and over again. But I can never figure out how to use recursion to solve a problem. Is there any systematic way to come up with a recursive solution?

Can someone please explain to me their thought process when they try to solve the following recursive problem: "Return all permutations of a string using recursion".

Here is an example of my thought process to solve this problem.

  • Check if the Strings length is equal to 2. If it is, swap the values (base case)
  • Else: for each first value return the first value + recursive(string without first value)

Can somebody please give me some tips to change my thought process or to think of recursion in a better way so I can solve recursive problems without just looking up the answers.

EDIT: Here is my thought process in coding another solution to this problem.

  • Base case is when the strings length = 0
  • If its not the base case, then for each first letter of the string, insert the first letter into every position of every permutation of the string without the first letter
  • Ex: string is "abc", first letter is a, so insert a in every position of the permutations of "bc". [bc, cb] => [abc, bac, bca, acb, cab, cba]

Pseudocode

permutation(String s, List l) {
   if(s.length() == 0) {
      return list;
   }
   else {
     String a = s.firstLetter();
     l = permutation(s.substring(1, s.length) , l)

     for(int i = 0; i < s.length(); i++) {            
        // loop that iterates through list of permutations 
        // that have been "solved"
        for(int j=0; j < l.size(); j++) {                 
           // loop that iterates through all positions of every 
           // permutation and inserts the first letter
           String permutation Stringbuilder(l[i]).insert(a, j);           
           // insert the first letter at every position in the 
           // single permutation l[i]
           l.add(permutation);
        }
     }
   }
}
Solution

  • The thought process:

    Given: a string.

    The goal: to construct a list containing all of its permutations.

    Types involved: permutations of a string is a list (collection) of strings where each is some permutation of the input string. String is a list (sequence) of characters.

    Analysis: string can be split into a head element (character) and the rest of elements, if not empty. Ergo, if we knew how to find permutations of rest, we could find permutations of whole, if we'd found a way to combine head with permutations-of-rest.

    Base case: the list containing all permutations of an empty string is a list of one empty string.

    Combination: for each permutation in permutations-of-rest (which is a list), insert head into each position between permutation's elements and also on both its ends, unless permutation was empty. In which case the string with one element, head, is the sole resulting permutation.

    Induction step: assume we already know how to permute the rest.

    Done.

    This kind of thing is known as "structural recursion" (cf. also this answer) or "fold" or "catamorphism": we tear apart an input, and combine the results of recursively applying our transformation on these parts, to get the combined result.

    string_permutations []     = [[]]
string_permutations (x:xs) = 
       for each p in string_permutations(xs):
          for each q in insert_everywhere(x,p): 
             yield q

    insert_everywhere(x,abc) must result in [ [xabc], [axbc], [abxc], [abcx]] and insert_everywhere(x,[]) must result in [ [x] ].

    yield means "put into the resulting overall collection".

    In a language with list comprehensions, the above could be written as

    string_permutations []     = [ [] ]
string_permutations (x:xs) = [ q | p <- string_permutations(xs)
                                 , q <- insert_everywhere(x,p) ]

    The principle is simple: deconstruct it into parts, do the parts recursively, combine the results. The trick of course is to keep it "true" at each step: to not violate some law about it, to not break some invariant about it. IOW the smaller problems must be "similar" to the bigger one: same laws must apply, same "theories" (i.e. "what we can rightly say about it") must apply.

    Usually, we should do the deconstruction in the most direct and simplest way possible. In our example we could have tried splitting the string into two halves -- but then the combination step would be non-trivial.

    Structural recursion is particularly easy: we're given a structure to begin with, which is usually defined as being built from its constituent parts, to begin with. :) You just need to learn to let go of the imperative hang-ups, like saying to yourself "How can I possibly deal with the sub-parts, while I'm not finished with the thing itself, yet?..".

    The mental trick is to imagine copies of yourself doing the same job for each of the sub-parts which are similar to the whole problem, following exactly the same set of rules, recipes and laws. And this is actually how a recursive call is done in the computer: a separate invocation -- a copy -- of the same procedure is made, but in a fresh new environment frame (on "the stack"). Then, when each copy is finished, it gives its results back to its invoker, which combines those results to form its results.

    (Ah, and reading SICP helps! :) )

    Recursion is a tool which is there to help us, to make programming easier.