Recursion

Recursive definitions are fairly common. We have already seen them in C, with array declarations, conditional statements and while loops. To see how to handle recursive situations, let us extend our pocket calculator to cope with the recursive possibility of parenthesised sub-expressions.

First here is a full syntax for arithmetic expressions.

expression
    term
    expression + term
    expression - term

term
    factor
    term * factor
    term / factor

factor
    identifier
    constant
    ( expression )
These definitions contain the recursive use of expression within parentheses and we wish to isolate this from the problem of operator precedence, which is implied by the separation into factors and terms each with their own set of operators. Thus below is a simplified syntax for our purposes. This also removes the non-constant definitions of factor.
expression
    factor
    factor + expression
    factor - expression
    factor * expression
    factor / expression

factor
    constant
    ( expression )
We are left with a problem which is solved by the following program.

Calculator for parentheses using recursion

#include 

float Expression() {
       char Operator, nextc;
       float Answer, NewNumber;
       
       Answer =0;
       Operator ='+';
       
       while ((Operator!='=') && (Operator!=')'))
       {
          nextc = getchar();
          
          if (nextc=='(') NewNumber =Expression(); else {
             ungetc(nextc,stdin);
             scanf("%f",&NewNumber);
          }
          
          switch (Operator) {
case '+':        Answer += NewNumber; break;
case '-':        Answer -= NewNumber; break;
case '*':        Answer *= NewNumber; break;
case '/':        Answer /= NewNumber; break;
          }    /* switch */
          
          Operator = getchar();
          
       }    /* end while loop */
       
       return Answer;
       
}    /* end Expression */ 

void main() {
    printf("Final answer is %f\n",Expression());
}
Plain text to compile and run.

The main program consists of a single statement, which is a call on printf. This has two parameters, the first simply a string constant, the second a call on the function float Expression.

Expression reads in and evaluates an expression. It allows any of the operators in our syntax. It terminates when it finds either a closing parenthesis, ')', or an equals sign, '='.

So long as the expression contains no parentheses, this program operates in the same way as our earlier calculator example. The difference is what it does with such sub-expressions. Note that the syntax only allows a left parenthesis, '(', at the start or after an operator, i.e. in the same place as a constant value. This means that we need to be able to look at the next character, to see if it is a left parenthesis, without necessarily keeping it.

The ungetch() puts back the last character read in. Thus, we can check if it is a '(' and still read it as the first character of a number if it is not. This is very useful, even if the idea used seems rather odd.

Handling sub-expressions

The case where a '(' is found is handled by replacing this character, using ungetc, and then calling Expression. After all, the syntax says that the '(' is always followed by an expression and the function Expression reads the expression which follows and returns its value. It does not matter that we are inside the body of Expression; it can call itself, recursively.

The second call of Expression is started by a '(' and ended by a ')'. It can never find a legal '='; only the first call of Expression can end with that. In fact it will end with the matching ')', even if there is another nested sub-expression inside this one.

To see this, let us examine an example. The expression (2+3*(3-(2-1))) would result in the following sequence:

"2+3*(3-(2-1))="
Call Expression #1 from scanf in main
    0+2=2;
    2+3=5; 
Find ( with Operator='*' and Answer=5

"3-(2-1))="
Call Expression #2
    0+3=3;
Find ( with Operator='-' and Answer=3;

"2-1))="
Call Expression #3 from Expression #2
    0+2=2; 
    2-1=1;
Find )

")="
End Expression #3
Return 1 to Expression #2
    3-1=2;
Find )

"="
End Expression #2;
Return 2 to Expression #1
    5*2=10;
Find =

""
End Expression #1
Return 10 to printf in main

Exercises on this section.


Next - Storage classes in C.

Back to Contents page.