java - 基本递归

Question

这是我从学校收到的作业问题。问题说，编写一个名为 capitalizer 的方法，它将接受字符串“ownage”，然后显示(不必返回)它所有可能的大写形式，例如“OwNaGE”或“OWnAGE”。它不必对每个字符串都起作用，只需“拥有”一词就足够了，而且必须通过递归来完成。

这是我目前所拥有的。

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

我现在脑子里一片困惑。好像我有很多重复的案例。你们认为我接近正确的解决方案了吗？我如何做到在基本情况下什么都不会发生而不是打印出一些东西？如何避免重复？任何人都请帮助我，我将不胜感激。

Answer 1

为了避免重复 - 你应该只在停止子句中打印你的字符串，而不是在每次迭代中。

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

算法的想法是:在每个阶段，您“猜测”当前字符是什么 - 它是大字符还是小字符，然后在较小的问题(使用下一个字符)上递归调用算法。
你对当前字母大写和不大写都重复这个。

---

前面的代码失败了，因为您打印了它在每次字母更改后生成的字符串，这导致比所有 2^n¹ 可能的方式多得多(几乎翻倍)打印单词。

---

(1) 奖励: 正好有 2^n 个可能的字符串可以打印，因为对于每个字符，您都需要选择:它是否大写？你对每个字符重复这个问题，从 rule of product - 它恰好为您提供了 2^n 个可能的字符串。