Solved

Mutual Recursion

Posted on 2008-10-02
9
398 Views
Last Modified: 2013-11-23
Hello

I am trying to implement what I *think* is mutual recursion - do correct me if I am wrong.

What I want is roughly the following (in rough pseudocode):

RunMethod(inputString, state, stack){
  if state is final state and string is empty
               return success
  if state is not final state but string is empty
               return failure
  if state is not final and string is not empty
              get all rules related to current state, symbol and string
  if there are no rules and the string is not empty
              return failure
  if there are rules and the string is not empty
      for each rule        
           take the rule and pass it to makeBranch method with current state, stack and symbol        
}

makeBranch(rule, string, state, stack){
 if state is final state and string is empty
               return success
  if state is not final state but string is empty
               return failure
  if state is not final and string is not empty
      change the state, stack and string according to the rule
      RunMethod(ChangedString, ChangedState, ChangedStack){
   
}


What is essentially happening is that this is a Push down Automata and I want it to find the rules it needs to implement. Take the first one and using that first one branch into a whole set of possibilities. But then I want it to GO BACK and consider the second rule and branch into all its possibilities and so on.
Currently all that happens is that the first branch gets considered - that's all. The program doesn't seem to go back to the beginning after running the first rule to run the second rule and its possibilities.

Can someone explain how I can do this with a simple example? I need to do this using JAVA as that is the only language I know.

public void initialCall (String filename, String inputString){

		//start state 

		String startState = reader.readStartState(filename);

		

		Stack<String> stackIs = new Stack<String>();

		//initialize the stack

		stackIs.add("Z0");

		System.out.println("stack- "+stackIs);

		

		ArrayList<Character> inputArray = inputDefine(inputString);

		System.out.println("intial call with "+inputArray);

		//PDAMatch(filename, inputArray, startState, stackIs);

		RUN(filename, inputArray, startState, stackIs);

		

}

	

public void RUN(String filename, ArrayList<Character> inputString, String newState, Stack newStack){
 

		ArrayList<Boolean> matched = new ArrayList<Boolean>();

		

		ArrayList<String> finalStates = reader.acceptBy(filename);

		finalStates.remove(0); //remove the letter 'F'
 

		System.out.println("input String:"+inputString);

	

		if (finalStates.contains(newState) && (inputString.isEmpty())){

			System.out.println("new state is final state and string all consumed: accepted");

			matched.add(true);

			//return matched;

		}
 

		if (!finalStates.contains(newState) && (inputString.isEmpty())){

			System.out.println("new state is NOT final state but string all consumed: rejected");

			matched.add(false);

			//return matched;

		}

		

		//the rules

		ArrayList<String[]> rule = new ArrayList<String[]>();

		System.out.println("BEGIN");

		if (!finalStates.contains(newState) && !inputString.isEmpty()){

		//	System.out.println( getRule(filename, inputString.get(0).toString(), newState, newStack));

			rule = getRule(filename, inputString.get(0).toString(), newState, newStack);

		}
 

		if (rule.isEmpty() && (!inputString.isEmpty())){

			System.out.println("stuck so rejected");

			//return matched;

		}

		

//		while (!rule.isEmpty() && !inputString.isEmpty()){

//			matched = makeBranch(filename, rule.get(0), inputString, newState, newStack);

//			rule.remove(0);

//		}

		if (!rule.isEmpty() && !inputString.isEmpty()){

		for (int i=0; i<rule.size(); i++){

			System.out.println(i);

			ArrayList<Boolean> temp = (makeBranch(filename, rule.get(i), inputString, newState, newStack));

			for (int j=0; j<temp.size(); j++){

				matched.add(temp.get(j));

			}

		

		}

		}

		System.out.println((matched));

		//return matched;

	}

	

	public ArrayList<Boolean> makeBranch(String filename, String[] strings, ArrayList<Character> inputString, String newState, Stack newStack) {
 

		ArrayList<Boolean> result = new ArrayList<Boolean>();

		

		//what are the accepting states

		ArrayList<String> finalStates = reader.acceptBy(filename);

		//System.out.println("finalStates- "+finalStates);

		finalStates.remove(0);

		//System.out.println("finalStates- "+finalStates);

		

		

		if (finalStates.contains(newState) && (inputString.isEmpty())){

			System.out.println("new state is final state and string all consumed: accepted");

			result.add(true);

		//	return result;

		}
 

		if (!finalStates.contains(newState) && (inputString.isEmpty())){

			System.out.println("new state is NOT final state but string all consumed: rejected");

			result.add(false);

		}

		

		System.out.println("input String:"+inputString);
 

		if (!inputString.isEmpty()){

		String[] row = strings;

		System.out.println("rule - " + Arrays.toString(row));

		

		//change stack

		ArrayList<String> stackWillBe = new ArrayList<String>();

		for (int j=4; j<((row.length)); j++){

			stackWillBe.add(row[j]);

		}	

		newStack = modifyTheStack(filename, inputString.get(0).toString(), newState, newStack, stackWillBe);

		System.out.println("new stack = "+ newStack);

		

		//consume input symbol if not epsilon transition

		System.out.println("check !row[1].equals(EPSILON)" + row[1]);
 

		if (!row[1].equals("EPSILON")){

			inputString.remove(0);

			System.out.println("copy of input Str after rem "+(inputString));

		}

		

		//change state

		newState = row[3];

		System.out.println("new state "+newState);

		

		//recursion: based on new state, symbol and stack find new branch

		RUN(filename, inputString, newState, newStack);

		}

		return result;

	}

Open in new window

0
Comment
Question by:ArtemisF
9 Comments
 
LVL 9

Expert Comment

by:mbodewes
Comment Utility
Answering this question would consist of creating a project in my favorite IDE and running it through the debugger. Have you already performed this feat yourself? Because just reading the (pseudo)-code and answering does seem to be a lot of work.
0
 
LVL 18

Expert Comment

by:JoseParrot
Comment Utility
By reading your pseudocode, I recognize it as mutual recursion.
There is a related article on mutual recursion at
http://cs.wellesley.edu/~cs111/spring00/lectures/mutual-recursion-example.html
which includes a very simple sample code.
Also a brief explanation at
http://en.wikipedia.org/wiki/Mutual_recursion
An obvious risk of such strategy is an endless recursion, so it is reccomendable to add some kind of control to stop it, like a counter ou user interruption.
About the code, I agree with mbodewes, it is very time consuming and difficult to say sometrhing about without reconstruct the development environment. I have assumed the code just as an implementation of your pseudocode, btw adequated to describe the case.
Jose

0
 

Author Comment

by:ArtemisF
Comment Utility
But is it not possible to give me an example of how in Java to make a method remember it has other stuff to do so it must go back and do that after it has finished one branch of mutual recursion?

I know what the issue is - I just do not know what I can do to solve it:

Here:
  for each rule        
           take the rule and pass it to makeBranch method with current state, stack and symbol        

It never takes the for each rule. As you can see in the code snippet I am asking it to go through all the rules but all it does is take the first one then heads off to the makeBranch method. Is there a way of making it simultaneously execute makeBrnach method for all the rules at the same time and then return all the answers for each of the branches it went off on?

The problem is every time Run gets called again it overwrites the rules to consider new ones which is what I want but then everytime it reaches the end I want the program to remember to go back one step and do the other rule, which is what is not happening.

Do I use global variables?  I don't know if that will help because again the global variable will get re-written...

I don't need you guys to tell me something specific about my code if that takes too much of your time but I would like to know if I can do something in Java where it can go off in a branch but then go back, see the conditions and go into another branch.


for (int i=0; i<rule.size(); i++){

			System.out.println(i);

			ArrayList<Boolean> temp = (makeBranch(filename, rule.get(i), inputString, newState, newStack));

			for (int j=0; j<temp.size(); j++){

				matched.add(temp.get(j));

			}

Open in new window

0
 
LVL 9

Expert Comment

by:mbodewes
Comment Utility
"I don't need you guys to tell me something specific about my code if that takes too much of your time but I would like to know if I can do something in Java where it can go off in a branch but then go back, see the conditions and go into another branch."

Gee, gosh, of course you can.

Some hints:
- don't use globals
- don't forget you cannot change parameters as they are pass by value
- you can use either an object state or a return value to switch on branches.
- make sure the states in which you return are well defined

There is nothing strange about mutual recursion, it's just recursion spread over two methods. The thing about the branches is that you need to remember when to return, and how deep you need to return. Just write it out on paper, and then program it. Check it not with print statements, but with a debugger.
0
Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 

Author Comment

by:ArtemisF
Comment Utility
Thank you for the reply, ok so "you cannot change parameters as they are pass by value" -- I am not sure what this means. You mean:

methodA(parameter 1, parameter 2){
     methodB(parameter 1, parameter 2)
}

methodB(parmeter 1, parameter 2){
   make changes to parameter 1
   make changes to parameter 2
    methodA(parameter1, paremeter 2)
}

So you mean I cannot do this? I should not be changing the parameters? But then I do need to change the parameters because I want it to go back to the first method and try things with the changed parameter. Should I be making clones (or something?) How can I do this?

"you can use either an object state or a return value to switch on branches."
Um no I don't think I get what you mean, sorry. Taking the example of methodA and methodB above in this comment you are saying that I can use what methodA returns to "switch on branches" (which means to know if methodB needs to be called or not?)

Would anyone know where I can find working examples to practice with of this sort of thing -- not just the simple mutual recursion but the whole concept of going back to consider other branches...

Thank you for your assistance and for being patient. I am new to this.
0
 
LVL 9

Accepted Solution

by:
mbodewes earned 250 total points
Comment Utility
With the warning: don't use global state. There should be no changes of global variables or fields within recursive functions. You may have a large static piece of data, as long as the access reference is kept within the stack. This is how recursion works: you keep the state using the stack. The disadvantage is that the stack can grow pretty quickly.

I've included an example, but I used the wikipedia example because I don't have a good case for mutual recursive methods. Maybe something with a tree or something would be better.

package mbodewes.ee;
 
 

public class MutualRecursive {

	private enum State {

		RUNNING, EVEN, ODD;

	}

	

	// works

	

	public State even(State state, int i) {

		if(i == 0) {

			return State.EVEN;

		}

		

		return odd(state, --i);

	}
 

	public State odd(State state, int i) {

		if(i == 0) {

			return State.ODD;

		}

		

		return even(state, --i);

	}
 

	// doesn't work

	

	public void wrongEven(State state, int i) {

		if(i == 0) {

			// doesn't do anything!

			state = State.EVEN;

			return;

		}

		

		odd(state, --i);

	}
 

	public void wrongOdd(State state, int i) {

		if(i == 0) {

			// doesn't do anything

			state = State.ODD;

			return;

		}

		

		even(state, --i);

	}

	

	public static void main(String[] args) {

		MutualRecursive rec = new MutualRecursive();
 

		State state = State.RUNNING;

		System.out.printf("Return: %s%n", rec.even(state, 8));

		

		state = State.RUNNING;

		state = rec.even(state, 9);

		System.out.printf("Return: %s%n", state);

		

		state = State.RUNNING;

		rec.wrongEven(state, 8); // will do nothing to the state

		System.out.printf("Return: %s%n", state);

	}
 

}

Open in new window

0
 
LVL 16

Assisted Solution

by:imladris
imladris earned 250 total points
Comment Utility
>  methodA(parameter 1, parameter 2){
       methodB(parameter 1, parameter 2)
   }

   methodB(parmeter 1, parameter 2){
      make changes to parameter 1
      make changes to parameter 2
       methodA(parameter1, paremeter 2)
   }

>So you mean I cannot do this?

Yes you can. The thing you may need to remember about pass by value is that any change made will not affect the *calling* code. For a simple example:

void foo()
{   int a=2;
     foobar(a);
     System.out.println("A: "+a);
}

void foobar(int a)
{   a=5;
     return;
}

The method foo will print 2; not 5. This is because the value of the a parameter is *copied* onto the stack for foobar to use. The foobar method can certainly change it, but it will not affect the original variable in foo. The advantage of this tactic is that foo is shielded against "unexpected" sideeffects to variables it passes to methods/functions.


So in your example you can change a parameter and pass this into the next function. You just can't expect that change to affect the value of the variable when the recursion bubbles back up to the calling method. So at the end of the *original* invocation of methodA, the value of param1 and param2 will be the same as when methodA started.
0
 

Author Comment

by:ArtemisF
Comment Utility
Thank you imladris & mbodewes for your help, I finally get it. Using the explainations you both gave above I tried writing a variation of the foo() and foobar(int a) thing and it did exactly what I wanted to so then I went back to my original program with this new knowledge of parameter passing and where the reurn statements should be and it worked!

The help was much appreciated.
	public static boolean foo(int a)

	{   

	if (a<=0){

			boolean matched = true;

			if (matched) System.exit(1);

		}

		ArrayList<Integer> list = new ArrayList<Integer>();

	    list.add(a);

	    list.add(a+4);

	    for (int i=0; i<list.size();i++){

	    	

	    	 System.out.println("A: "+foobar(list.get(i)));

	    }

	return false;

	}
 

	public static boolean foobar(int a)

	{   a=a-5;

	    return foo(a);

	}

Open in new window

0
 

Author Closing Comment

by:ArtemisF
Comment Utility
Thank you for the help. Since both Experts contributed to my understanding I have divided the points evenly.
0

Featured Post

Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
This tutorial covers a practical example of lazy loading technique and early loading technique in a Singleton Design Pattern.
This video teaches viewers about errors in exception handling.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now