Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Mutual Recursion
Author Message
Shah-Cuber

Posted: Sat Aug 01, 2009 11:43 am   Post subject: Mutual Recursion

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 '='" + " ( 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 '=' ( 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

Posted: Sun Aug 02, 2009 4:05 pm   Post subject: RE:Mutual Recursion

interesting... good work
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 2 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: