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

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.