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;
} Example 4.6
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--;
}
} Example 4.7
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);
} Example 4.8
Footnotes
|