Counting, without using a Loop

This is a problem which might come up during a job interview, to try to figure out, how do you think. And it goes something like: “Can you count (i.e. print each number), from 1 to 100, without using a loop?”

Now some languages will have some special functions which you can use to do this, however, I want to show something that will work in almost any language – and that is recursion. Recursion of course is the process of a function calling itself again and again, until an ending condition is met.

Below, I’ll use C++ to demonstrate this in three levels of complexity:

Simple Recursion

Here, were going to assume the ending value and hard code it in. This is fast to write, efficient to run, but limits what you can do with it.

void notALoop(int current ) {
  // test our exit/stop behavior to see if we run this iteration
  if(current < 100) {
    // print out our current number
    cout << current << endl;
    // recursively call our function, incrementing current by one
    notALoop(current + 1);
  }
}
int main() {
  notALoop(1);
}

Medium Complexity Recursion

In this case, we’ll create a function overload. This way, you don’t have to exit at 100, you can simply offer a second, option parameter.

void notALoop(int current ) {
  // test our exit/stop behavior to see if we run this iteration
  if(current < 100) {
    // print out our current number
    cout << current << endl;
    // recursively call our function, incrementing current by one
    notALoop(current + 1);
  }
}
// the same function, but overloaded with an optional end parameter
void notALoop(int current, int end ) {
  // test our exit/stop behavior to see if we run this iteration
  if(current < end) {
    // print out our current number
    cout << current << endl;
    // recursively call our function, incrementing current by one
    notALoop(current + 1, end);
  }
}
int main() {
  notALoop(1);
  notALoop(1,25);
}

Advanced Complexity Recursion

In this case, we opt for a feature that not all languages have, and thus some people avoid it: default values of parameters.

void notALoop(int current, int end = 100 ) {
  // test our exit/stop behavior to see if we run this iteration
  if(current < end) {
    // print out our current number
    cout << current << endl;
    // recursively call our function, incrementing current by one
    notALoop(++current);
  }
}
int main() {
  notALoop(1);
  notALoop(1,25);
}

Notice also that we used ++current, instead of current + 1. Functionally they are the same, however, some compilers optimize the ++ to be faster. Also notice that we used ++current instead of current++. In many cases, these two calls are identical, however, the ++current occurs before the function is called, so the recursive call gets updated. The current++ would occur once the function call returns, and thus you’d get into an infinite recursion situation.

Counting, without using a Loop was originally found on Access 2 Learn