Mutual Recursion

[Shah-Cuber]

Mutual Recursion

Woke up this morning, thought I might post a quick tutorial, though I wouldn't really call it a tutorial - on mutual recursion (Recently, some people have been asking me to do so), so ... enjoy ...

We've all have done recursion in the past (If you haven't ... do so), in which methods call themselves, etc .... However, an indirect form of recursion occurs when one method calls another, which in turn calls the first. This is Mutual Recursion. So for a simple example, I thought I might do a expression evaluator. I have constructed three methods, called Expression, Term, and Primary, that are mutually recursive. The method Expression calls Term, Term calls Primary, and Primary calls Expression. The task of the main method that uses these methods is to compute the value of an arithmetic expression containing only real numbers with the addition (+), subtraction (-), multipication (*), and division (/) operators, and parentheses. For example, if the input expression is:

1.5 + 3.0 * ( 0.5 + 1.5 )

The output would be 7.5.

The input expression must have spaces between the tokens, that is, between the numerical values and operators or parentheses, and there must be a final dummy token, such as the equal sign, to signal the end of the expression.

The program (In Java) evaluates an input expression e of the form t{ + t} where t is of the form p{* p} and p is of the form (e) or an explicit real constant such as 1.5. The braces, { and }, are used to indicate zero or more copies of the enclosed items. We can describe these expressions to be evaluated using this mathematical notation:

e -> t{ + t}
t -> p{* p}
p -> (e) | real constant

In this notation, -> means "expands to" and | means a choice between two possible expansions.

Here is the main program called ExpressionEvaluator (done in 10 min =P) that contains the three methods Primary, Term, and Expression. As well, there is a method Evaluate that is called by the main method after a line containing the expression to be evaluated has been read in and an ExpressionEvaluator object has been instantiated. The constructor converts the input string line into a StringTokenizer object to initialize the values of the instance variables tokenizer, and token.

code:

/*  * The "ExpressionEvaluator" class.  * Computes the value of simple arithmetic expressions.  * It does almost no error checking. It also requires  * that each element of the expression be seperated by  * spaces.  */    import java.io.*;    import java.util.*;     public class ExpressionEvaluator    {       protected StringTokenizer tokenizer;       protected String token;            // Initialize the tokenizer with the String line        public ExpressionEvaluator(String line) // Constructor       {          tokenizer = new StringTokenizer(line);          token = tokenizer.nextToken();       }            // Evaluate the expression used to instantiate the object        public double Evaluate()       {          return Expression();       }            // Evaluate an expression in parentheses or a single number        protected double Primary()       {          double result;                if(token.equals("("))          {             token = tokenizer.nextToken();             result = Expression();          }          else          {             result = Double.valueOf(token).doubleValue();          }                token = tokenizer.nextToken();          return result;       }          /*       * Evaluate a multipication expression: primary * primary       * Evaluate a Division expression: primary / primary       */        protected double Term()       {          double nextValue;          double result;                result = Primary();                while(token.equals("*"))          {             token = tokenizer.nextToken();             nextValue = Primary();             result *= nextValue;          }                  while(token.equals("/"))          {             token = tokenizer.nextToken();             nextValue = Primary();             result /= nextValue;          }                return result;       }          /*       * Evaluate a addition expression: term + term       * Evaluate a subtraction expression: term - term       */        protected double Expression()       {          double nextValue;          double result;                result = Term();                while(token.equals("+"))          {             token = tokenizer.nextToken();             nextValue = Term();             result += nextValue;          }                  while(token.equals("-"))          {             token = tokenizer.nextToken();             nextValue = Term();             result -= nextValue;          }                return result;       }            public static void main (String[] args)throws IOException       {          DataInputStream in = new DataInputStream(System.in);          String line;                while(true)          {             System.out.print("Enter an expression ending with '='" + " (<ENTER> to quit): ");             line = in.readLine();                       if(line.length() == 0)             {                break;             }                       ExpressionEvaluator expn = new ExpressionEvaluator(line);             System.out.println(line + " " + expn.Evaluate());          }       }    }

Which may result an output such as, assuming the input was:

code:

Enter an expression ending with '=' (<ENTER> to quit): 1.5 + 3.0 * ( 0.5 + 1.5 ) = 1.5 + 3.0 * ( 0.5 + 1.5 ) = 7.5

Hope that helps out ...

Note: This tutorial is for people who are starting to program as beginners. There are much better ways to do an expression evaluator program ... More experienced programmers might wanna try http://compsci.ca/v3/viewtopic.php?t=21597&highlight=163

[matt271]

interesting... good work