Example on indirect recursion¶

Reading instruction

You need not worry, if you do not understand this example.

According to earlier material, indirect recursion means the situation where the function A calls function B, and B calls A.

As an example on indirect recursion, we will consider how to parse and evaluate an expression. Parsing checks if the given expression follows a certain format, i.e. if it follows the given grammar.

Grammar for the expression¶

An expression can be given with the following grammar:

<Expr> ::= <Term> + <Expr> | <Term> - <Expr> | <Term>
<Term> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ( <Expr> )

The grammar above is written in BNF (Backus-Naur Form). Now nonterminal symbols are enclosed with arrow brackets, while terminal symbols are written as such.

As terminal symbols, the grammar accepts one-digit numbers (0 - 9), operators + and -, and parentheses. The grammar accepts, for example, the following expressions:

2+3
2+3-4
1-(2+3)
(2+3)
((2+3))
1+(6-7)-(2+4+5+(2+3))

If an expression follows the grammar, the expression can be derived from the grammar by applying either one of the two grammar rules as many times as needed. For example, the expression 1 - (2 + 3) can be derived as follows:

<Expr>
     -> <Term> - <Expr>
     -> 1 - <Expr>
     -> 1 - <Term>
     -> 1 - ( <Expr> )
     -> 1 - ( <Term> + <Expr> )
     -> 1 - ( 2 + <Expr> )
     -> 1 - ( 2 + <Term> )
     -> 1 - ( 2 + 3 )

Program code¶

The program code to be considered can be found from the directory examples/02/expression/. The program parses the given expression, and if the expression follows the grammar, the program also evaluates it.

Besides the main function, the program has two more functions, one for each grammar rule: parse_term and parse_expr. Each of them calls the other, i.e. we have an indirect recursion. Therefore, at least one of the functions requires forward declaration.

Recursion can also be seen in the grammar: <Term> occurs in the <Expr> rule and <Expr> occurs in the <Term> rule.

These two functions have been implemented in a very straightforward way based on the grammar. For example, function parse_term considers first the cases, where term is a number (digit). After that it considers the case, where term is an expression enclosed by parentheses. In this case, it skips the left parenthesis and calls recursively the function parse_expr. Finally, it skips the right parenthesis.

In a similar way, the function parse_expr considers different cases separately. An expression can be just a term (as a number like 2), or it can consist of two terms separated by a plus sign (as 2+3), or it can consist of two terms separated by a minus sign (as 2-3). In every case, the first part of an expression is a term, and thus, the function first calls the function parse_term recursively. After that it checks if there is an operator (+ or -) and evaluates the expression accordingly.

About the usefulness of recursion¶

A program like this would be very difficult to implement without recursion. Therefore, recursion is a useful topic to be learned. The program could be easily extended to consider also multiplication and division. Or, if the grammar had more rules, we could easily (in a straightforward way) implement functions for them.