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

Question

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);
        }
     }
   }
}

Answer 1

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.

Answer 2

Thinking recursive

I think, that for understanding a complex concept you should start fro a joke (but correct) explanation.

So, take the definition of the Recursive Salad:

Recursive Salad is made of apples, cucumbers and Recursive Salad.

As for analyzing, it is similar to the Mathematical Induction.

• You have to define the base - what will happen, when the work is already done and we have to end. Write this part of code.
• Imagine how the process should step from ALMOST finished task to the finished task, how we can do that last step. Help yourself with writing the code for the last step.
• If you can't abstract yet to step last-N, create code for the last-1. Compare, abstract it.
• Do that last-N step finally
• Analyze what is to be done when you come to the start.

How to solve a task

'breaking solution into smaller cases' is far from being enough. The main rule is: Every mathematical task more complex than 2x2, should be solved from the end. Not only recursive ones. If you will follow that rule, maths will become a toy for you. If you won't, you shall always have serious problems with solving any task other way than by accident.

The way of setting of your task is bad. You must solve the task, not solve the task by ANYTHING concrete. Start from the target, not from the tool or data given. And move to the data step by step, sometimes using some methods that are convenient. The recursive solution should come to you naturally, by itself. Or it shouldn't and you'll do it other way.

Read the book "How to Solve It" of G.Polya. If your math/IT teacher haven't advised it, he should be fired. The problem is, that 99% of them should be fired... :-(. And don't think, that citations on the internet will be enough. Read THE book. It is the king's way into maths.

---

How to think recursive - example

(The code is NOT real Java) (the code is not intended to be effective)

We need: a list of permutations for a string with all different chars.

It can be written as List

So, the function, when it will be ready, will take the string to be permutated and return that list

List<String> allPermutations(String source){}

To return that list, the function has to have such list as a local variable.

List<String> allPermutations(String source){
  List<String> permutResult=new List<String>();
  return permutResult;
}

Let's imagine we have found already permutations of almost the whole string, but the last char in it.

List<String> allPermutations(String source){
  List<String> permutResult=new List<String>();
  ...we have found permutations to all chars but the last
  We have to take that last char and put it into every possible place in every already found permutation.
  return permutResult;
}

But that already found permutations we could write as our function for a bit shorter string!

List<String> allPermutations(String source){
  List<String> permutResult=new List<String>();
  permutFound=allPermutations(substr(source,source.length-1));
  for (String permutation: permutFound){
    for (int i=0;i<=permutation.length;i++){
      String newPermutation=permutation.insert(source[last],i);
      permutResult.add(newPermutation);
    }
  }
  return permutResult;
}

It is a pleasure, we don't need to count and use the current length of the source string - we are constantly working with the last char... But what about the start? We can't use our function with the empty source. But we can change it so, that we shall be able to use it so! For the start we need one permutation with empty string. let's return it, too.

List<String> allPermutations(String source){
  List<String> permutResult=new List<String>();
  if (source.length==0){
    permutResult.add("");
  }     
  permutFound=allPermutations(substr(source,source.length-1));
  for (String permutation: permutFound){
    for (int i=0;i<=permutation.length;i++){
      String newPermutation=permutation.insert(source[last],i);
      permutResult.add(newPermutation);
    }
  }
  return permutResult;
}

So, finally we made the program to work at start, too. That's all.

Answer 3

You can try thinking about how you would solve the problem having a solution to a simpler problem. How would you solve the problem of size i if you already have a solution to the problem of size i-1, or how would you solve the problem at step i if the step i-1 and all the previous steps are already solved.

The recursion is thinking by induction [1].

In the case of permutations, your base case is ok, (it could also be an empty string or string with 1 element, the permutation of that string is the same string).

But your induction step fails, try thinking that if your string is of length i, and you already have a set of all the permutations of strings of length (i-1), how would you create all the permutations of the string by having that additional i-th character?

Now it helps to think in small cases, like 2 elements: {"ab", "ba"} What if you are given a third element "c", how do you create permutations of the string "abc" using the above elements and the solution to "ab"?

Well the answer is: {"cab", "acb", "abc", "cba", "bca", "bac"}

Note where "c" goes, it gets inserted at every position for each string in the previous solution. That is (pseudocode):

res = {}
for s in {"ab", "ba"}:
  for i = 0 to len(s):
    res.add(s.insert("c", i))

Now replace {"ab", "ba"} by a recursive call with a i-1 string and you have the recursion function.

Feel free to ask if this is not clear enough.

Answer 4

I think recursion is the more intuitive way of solving if you get familiar with it. Simple rule is that imagine your function as a combination of the same function with smaller inputs. There are cases where recursion is more visible than others. For example permutations is one such case. Just imagine permut(S) = List{a+permut(S-{a})} for all a in S where S consists of unique characters. Idea is to select a character in string and concatenate it with all permutations of the remaining characters this will give all unique permutations of string starting with that character.

Example pseudo code : -

Permutation(S,List) {

    if(S.length>0) {

        for all a in S {

            Permutation(S.remove(a),List.add(a));
        }

    }

    else  print List;

 }

The above code is according to me most simple to understand for permutation because it directly translates the recurrence relation where in we select a character from string and then concatenate it all other combinations of smaller string.

Note:- This can be done more efficiently using array and swapping but it is more complex for understanding.