Loop through numbers from 0 to 100 and print out every third number without the modulo function using recursion

Question

I had an interview the other day that asked the question, loop through the numbers from 0 to 100 and print out every third number. This is a very easy question if you know what the modulo function is. So I came up with the solution (Note I was using Java):

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

He then asked, what if you can't use division or the modulo function. So I had to think about this for about 30 seconds, and came up with a solution, that I knew was very inefficient, and let him know it was very inefficient, but would work.

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

I'm free writing this without testing, so it might not work 100%, but you get the idea of how I solved the problem. He said he understood what I was trying to do. He then said that there is another way to do it using a recursive function. He tried to briefly explain it to me, but I didn't understand how you could use a recursive function to solve this problem. Can anyone come up with a solution using recursion?

EDIT:

Thanks for all the answers! I didn't think this question would attract as much attention as it did, but I appreciate all the answers. Some of you didn't understand that you can ONLY increment by 1. So you must loop through every natural number from 0 to 100.

Answer 1

There is a cool trick to test if a number is divisible by three. If the sum of all its digits is divisible by three, then the original is divisible by three. This can be applied recursively: if I have a number a, I can add all the digits of a together to get b and see if b is divisible by 3. How do I know if b is divisible by three? Add all of its digits together to get c and see if c is divisible by three...

As with all recursion, you have to stop at some point. The base case is when you have a sum which is only one digit long- you can have a list of digits divisible by three and check against these. In code:

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

Answer 2

As no answer has been picked yet I like to add my two cents here. Since the trick is do the modulo function with recursion and without division (as I understood) here is my solution:

public static void main(String[] args) {
    for ( int i = 1; i <=100; i++ ){
        if ( mod(i, 3) ){
            System.out.println(i);
        }
    }
}

public static boolean mod(int a, int b){
    if ( a < 0 ){
        return false;
    }else if (a==b){ 
        return true;
    }else{ 
        return mod( a-b, b );
    }
}

EDIT

This version will handle division by 0 and negative numbers on the modulo function:

public static boolean mod(int a, int b){
    if ( b < 0 ){
        b=b*-1;
    } 
    if ( a < 0 || b == 0){
        return false;
    }else if (a==b){ 
        return true;
    }else{ 
        return mod( a-b, b );
    }
}