java - 循环从 0 到 100 的数字，并使用递归打印出每三个数字而不使用模函数

Question

前几天我接受采访时问了这个问题，循环遍历从 0 到 100 的数字并打印出每三个数字。如果您知道模函数是什么，这是一个非常简单的问题。所以我想出了解决方案(注意我使用的是 Java):

for (int i=0; i<100; i++) {
  if (i % 3 == 0) {
    System.out.println(i);
  }
}

然后他问，如果不能使用除法或取模函数怎么办。所以我不得不考虑大约 30 秒，想出了一个解决方案，我知道这个解决方案效率很低，并且让他知道它效率很低，但会奏效。

int x = 3;
for (int i=0; i<100; i++) {
  for (int j=0; j<33; j++) {
    if (x*j==i) {
      System.out.println(i);
      break;
    } 
  }
}

我是在没有测试的情况下自由编写的，所以它可能无法 100% 工作，但你知道我是如何解决这个问题的。他说他明白我想做什么。然后他说还有另一种方法可以使用递归函数来完成。他试图向我简要解释一下，但我不明白如何使用递归函数来解决这个问题。谁能想出一个使用递归的解决方案？

编辑:

谢谢大家的回答!我不认为这个问题会引起如此多的关注，但我很感激所有的答案。你们中有些人不明白你只能递增 1。所以你必须循环遍历从 0 到 100 的每个自然数。

Answer 1

有一个cool trick to test if a number is divisible by three .如果它所有数字的和能被三整除，那么原数能被三整除。这可以递归地应用:如果我有一个数字 a，我可以将 a 的所有数字加在一起得到 b 并查看是否 b 可以被 3 整除。我怎么知道 b 是否可以被 3 整除？将其所有数字相加得到 c 并查看 c 是否可以被三整除...

与所有递归一样，您必须在某个时刻停止。基本情况是当你有一个只有一位数长的总和时——你可以有一个可被三整除的数字列表并检查这些数字。在代码中:

public boolean printDivisibleByThrees(){
    for(int i=0; i<100; i++){
        if(isDivisibleByThree(i)){
            System.out.println(i);
        }
    }
}

public boolean isDivisibleByThree(int i){
    if(i<0){
        i = -1*i; //we only care about the absolute value of i
    }
    if(Arrays.asList(0,3,6,9).contains(i)){
        return true;
    } else if(i<10){
        return false; //one digit number not divisible by three
    } else {
        int j = sumDigits(i);
        return isDivisibleByThree(j);
    }
}

public int sumDigits(int i){
    String iString = (new Integer(i)).toString();

    int sum = 0;
    for(char digit : iString.toCharArray()){
        sum += (new Integer(digit+"")).intValue();
    }

    return sum;
}