4.3. Recursion and argument passing

So far, we've seen how to give functions a type (how to declare the return value and the type of any arguments the function takes), and how the definition is used to give the body of the function. Next we need to see what the arguments can be used for.

4.3.1. Call by value

The way that C treats arguments to functions is both simple and consistent, with no exceptions to the single rule.

When a function is called, any arguments that are provided by the caller are simply treated as expressions. The value of each expression has the appropriate conversions applied and is then used to initialize the corresponding formal parameter in the called function, which behaves in exactly the same way as any other local variables in the function. It's illustrated here:

void called_func(int, float);

main(){
      called_func(1, 2*3.5);
      exit(EXIT_SUCCESS);
}

void
called_func(int iarg, float farg){
      float tmp;

      tmp = iarg * farg;
}

The arguments to called_func in main are two expressions, which are evaluated. The value of each expression is used to initialize the parameters iarg and farg in called_func, and the parameters are indistinguishable from the other local variable declared in called_func, which is tmp.

The initialization of the formal parameters is the last time that any communication occurs between the caller and the called function, except for the return value.

For those who are used to FORTRAN and var arguments in Pascal, where a function can change the values of its arguments: forget it. You cannot affect the values of a function's actual arguments by anything that you try. Here is an example to show what we mean.

#include <stdio.h>
#include <stdlib.h>
main(){
      void changer(int);
      int i;

      i = 5;
      printf("before i=%d\n", i);
      changer(i);
      printf("after i=%d\n", i);
      exit(EXIT_SUCCESS);
}

void
changer(int x){
      while(x){
              printf("changer: x=%d\n", x);
              x--;
      }
}

The result of running that is:

before i=5
changer: x=5
changer: x=4
changer: x=3
changer: x=2
changer: x=1
after i=5

The function changer uses its formal parameter x as an ordinary variable—which is exactly what it is. Although the value of x is changed, the variable i (in main) is unaffected. That is the whole point—the arguments in C are passed into a function by their value only, no changes made by the function are passed back.

4.3.2. Call by reference

It is possible to write functions that take pointers as their arguments, giving a form of call by reference. This is described in Chapter 5 and does allow functions to change values in their callers.

4.3.3. Recursion

With argument passing safely out of the way we can look at recursion. Recursion is a topic that often provokes lengthy and unenlightening arguments from opposing camps. Some think it is wonderful, and use it at every opportunity; some others take exactly the opposite view. Let's just say that when you need it, you really do need it, and since it doesn't cost much to put into a language, as you would expect, C supports recursion.

Every function in C may be called from any other or itself. Each invocation of a function causes a new allocation of the variables declared inside it. In fact, the declarations that we have been using until now have had something missing: the keyword auto, meaning ‘automatically allocated’.

/* Example of auto */
main(){
      auto int var_name;
      .
      .
      .
}

The storage for auto variables is automatically allocated and freed on function entry and return. If two functions both declare large automatic arrays, the program will only have to find room for both arrays if both functions are active at the same time. Although auto is a keyword, it is never used in practice because it's the default for internal declarations and is invalid for external ones. If an explicit initial value (see ‘ initialization’) isn't given for an automatic variable, then its value will be unknown when it is declared. In that state, any use of its value will cause undefined behaviour.

The real problem with illustrating recursion is in the selection of examples. Too often, simple examples are used which don't really get much out of recursion. The problems where it really helps are almost always well out of the grasp of a beginner who is having enough trouble trying to sort out the difference between, say, definition and declaration without wanting the extra burden of having to wrap his or her mind around a new concept as well. The chapter on data structures will show examples of recursion where it is a genuinely useful technique.

The following example uses recursive functions to evaluate expressions involving single digit numbers, the operators *, %, /, +, - and parentheses in the same way that C does. (Stroustrup¹, in his book about C++, uses almost an identical example to illustrate recursion. This happened purely by chance.) The whole expression is evaluated and its value printed when a character not in the ‘language’ is read. For simplicity no error checking is performed. Extensive use is made of the ungetc library function, which allows the last character read by getchar to be ‘unread’ and become once again the next character to be read. Its second argument is one of the things declared in stdio.h.

Those of you who understand BNF notation might like to know that the expressions it will understand are described as follows:

<primary> ::= digit | (<exp>)
<unary>   ::= <primary> | -<unary> | +<unary>
<mult>    ::= <unary> | <mult> * <unary> |
              <mult> / <unary> | <mult> % <unary>
<exp>     ::= <exp> + <mult> | <exp> - <mult> | <mult>

The main places where recursion occurs are in the function unary_exp, which calls itself, and at the bottom level where primary calls the top level all over again to evaluate parenthesized expressions.

If you don't understand what it does, try running it. Trace its actions by hand on inputs such as

1
1+2
1+2 * 3+4
1+--4
1+(2*3)+4

That should keep you busy for a while!

/*
* Recursive descent parser for simple C expressions.
* Very little error checking.
*/

#include <stdio.h>
#include <stdlib.h>

int expr(void);
int mul_exp(void);
int unary_exp(void);
int primary(void);

main(){
      int val;

      for(;;){
              printf("expression: ");
              val = expr();
              if(getchar() != '\n'){
                      printf("error\n");
                      while(getchar() != '\n')
                              ; /* NULL */
              } else{
                      printf("result is %d\n", val);
              }
      }
      exit(EXIT_SUCCESS);
}

int
expr(void){
      int val, ch_in;

      val = mul_exp();
      for(;;){
              switch(ch_in = getchar()){
              default:
                      ungetc(ch_in,stdin);
                      return(val);
              case '+':
                      val = val + mul_exp();
                      break;
              case '-':
                      val = val - mul_exp();
                      break;
              }
      }
}

int
mul_exp(void){
      int val, ch_in;

      val = unary_exp();
      for(;;){
              switch(ch_in = getchar()){
              default:
                      ungetc(ch_in, stdin);
                      return(val);
              case '*':
                      val = val * unary_exp();
                      break;
              case '/':
                      val = val / unary_exp();
                      break;
              case '%':
                      val = val % unary_exp();
                      break;
              }
      }
}

int
unary_exp(void){
      int val, ch_in;

      switch(ch_in = getchar()){
      default:
              ungetc(ch_in, stdin);
              val = primary();
              break;
      case '+':
              val = unary_exp();
              break;
      case '-':
              val = -unary_exp();
              break;
      }
      return(val);
}

int
primary(void){
      int val, ch_in;

      ch_in = getchar();
      if(ch_in >= '0' && ch_in <= '9'){
              val = ch_in - '0';
              goto out;
      }
      if(ch_in == '('){
              val = expr();
              getchar();      /* skip closing ')' */
              goto out;
      }
      printf("error: primary read %d\n", ch_in);
      exit(EXIT_FAILURE);
out:
      return(val);
}

Footnotes

1. Stroustrup B. (1991). The C++ Programming Language 2nd edn. Reading, MA: Addison-Wesley