Solved

Mutual Recursion

Posted on 2008-10-02
9
404 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
9 Comments
 
LVL 9

Expert Comment

by:mbodewes
ID: 22624755
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:Jose Parrot
ID: 22627443
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
ID: 22629234
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
Online Training Solution

Drastically shorten your training time with WalkMe's advanced online training solution that Guides your trainees to action. Forget about retraining and skyrocket knowledge retention rates.

 
LVL 9

Expert Comment

by:mbodewes
ID: 22629733
"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
 

Author Comment

by:ArtemisF
ID: 22629819
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
ID: 22630500
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
ID: 22635152
>  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
ID: 22639672
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
ID: 31502311
Thank you for the help. Since both Experts contributed to my understanding I have divided the points evenly.
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Are you developing a Java application and want to create Excel Spreadsheets? You have come to the right place, this article will describe how you can create Excel Spreadsheets from a Java Application. For the purposes of this article, I will be u…
In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
Video by: Michael
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …
The viewer will learn how to implement Singleton Design Pattern in Java.

717 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