Sign in to follow this  
Concentrate

Recursive Problem

Recommended Posts

This is in java. I am confused on how to do this. I have to use the Deque interface to print the deque backwards, i.e from back to front. Here is the Deque interface :
public interface Deque<E> {
	public int size();
	public boolean isEmpty();
	public E getFirst() throws EmptyDequeException;
	public E getLast() throws EmptyDequeException;
	public void addFirst (E element);
	public void addLast (E element);
	public E removeFirst() throws EmptyDequeException;
	public E removeLast() throws EmptyDequeException;
	
}
Here is what I have :
static void _recursivePrint(Deque deque) throws EmptyDequeException{
	if(deque.isEmpty())
		return;
	else {
		print(deque.getLast() + "  "); //use overloaded print
		deque.removeLast();
		_recursivePrint(deque); //recursive call it
	}
}
Its all good, but for one problem. The problem is that I am required not to change the original deque's structure. Anyone have any ideas they can throw at me? I can't clone deque because its not provided in the interface of deque.

Share this post


Link to post
Share on other sites
Since the interface appears to allow access only to the first or last item, you might consider something like the following:

removeLast() item and print it
addFirst() to put it at the front of the list
Repeat this until you get back to the first item you selected.

By removing an item from the back and inserting it at the front, you'd just be rotating the list; eventually, each item would end up in the same position in which it started.

That's the best I've got to offer at this late hour. :-)

Share this post


Link to post
Share on other sites
I gather this isn't java.util.Deque.

You could do this:

    static void _recursivePrint(Deque deque)
{
_recursivePrint(deque, deque.getLast());
}


static void _recursivePrint(Deque deque, Object start)
{
if(deque.isEmpty())
return;

System.out.print(deque.getLast() + " "); //use overloaded print
deque.addFirst(deque.removeLast());

if (deque.getLast() == start)
return;

_recursivePrint(deque, start); //recursive call it
}



I wouldn't use recursion, though. God-awful, repugnant functional code. *shudder*

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this