Exercise: Reverse Input

We just discussed recursive functions, and the following exercise shows you one example of recursion which is less trivial than a factorial.

What happens if a recursive function has a local variable, e.g. int c? When the function calls itself, the created stack frame will have another instance of the variable c: each function has its own variable.

void f() {
  int c;
  ...
  if (...) { /* base case: make sure you exit the function */
    return;
  }

  /* recursive call */
  f(); /* will have its own c! */
}

So, if it happened so that f was called 5 times, there will be a moment when there are five stack frames with 5 different variables int c, each of them accessible from their own instance of f.

Why do we need that, and how to use it?

In this exercise, let's try implementing a function void reverse() which uses getchar() to read the input until it ends (getchar() returns EOF), and prints all the characters in reverse (using putchar(c)). I'll ask you to do it without knowing the size of the input (assuming it's reasonable), and without making an array or allocating any memory, except for just one variable, int c, in function reverse.

Try to do it, and scroll down to read some explanations below the code box.

#include <stdio.h>

void reverse() {
  int c;
  /* TODO: write the code */
}

int main() {
  reverse();
  return 0;
}

The idea here is that each invocation of reverse() will read one character by calling getchar() once. If it returns EOF, that's your base case, and you exit. But if it's not EOF, you first call reverse() recursively, and only after it returns, you print your c using putchar(c).

At the end of input, you will have multiple stack frames, each of which will have one character in its own instance of c. Then, as the deepest recursive reverse() returns, the last c will be printed. After that, one more reverse() returns, and one more c is printed, and so on, until the first call to reverse() completes, which completes the main() function.

Here we used recursion to actually store some data, without creating any array. In the future we'll see more examples of this!