Basic recursion

Question

This is an assignment question I received from school. The question says, write a method called capitalizer which will take the string "ownage" and then displays(doesn't have to return) all the possible capitalization of it, such as "OwNaGE" or "OWnAGE". It doesn't have to work for every string, just the word "ownage" is enough, and it has to be done with recursion.

Here's what I have so far.

import java.util.*;

class MethodAssign2{
   static void capitalizer(String a,int b){
      if(b==-1){
         System.out.println("worked?");
      }else{
         char[] achars = a.toCharArray();
         achars[b] -= 32;
         String caplet = new String(achars);
         System.out.println(caplet);
         System.out.println(a);
         capitalizer(caplet,b-1);
         capitalizer(a,b-1);
      }
   }
   public static void main(String[]args){
      String word = "ownage";
      capitalizer(word,word.length()-1);
   }
}

My mind is completely messed up right now. It seems like I have lots of repeated cases. Do you guys think I'm close the right solution? How do I make it so that nothing happens in the base case rather than printing out something? How do I avoid the repeats? Anyone please help me I would appreciate it very much.

Answer 1

To avoid the repeats - you should print your string only in the stop clause, and not in every iteration.

static void capitalizer(String a,int b){
    if(b==-1){
        System.out.println(a); //CHANGE: printing in the stop clause
    }else{
        char[] achars = a.toCharArray();
        achars[b] -= 32;
        String caplet = new String(achars);
        //CHANGE: not printing every iteration
        capitalizer(caplet,b-1);
        capitalizer(a,b-1);
    }
}

The idea if the algorithm is: In each stage you "guess" what is the current character - is it an upper or lower character, and invoke the algorithm recursively on the smaller problem (with the next character).
You repeat this for both the current letter is and is not capitalized.

---

The previous code failed because you printed the strings it generated after every letter change, which results in much more (almost double) then all 2^n¹ possible ways to print the word.

---

(1) Bonus: There are exactly 2^n possible strings you can print, because for every character you need to chose: Is it capitalized or not? You repeat this question for each character, and from rule of product - it gives you exactly 2^n possible strings.