Recursion with Sequences

  • (2 Pages)
  • +
  • 1
  • 2

19 Replies - 541 Views - Last Post: 16 May 2014 - 04:47 PM Rate Topic: -----

#1 PreDominance  Icon User is offline

  • New D.I.C Head

Reputation: 5
  • View blog
  • Posts: 14
  • Joined: 14-May 14

Recursion with Sequences

Posted 14 May 2014 - 04:11 PM

So I have a small recursion problem.

I have a function that performs perfectly iteratively (non-recursively, with a loop). What it does, is it takes the average of adjacent elements in a Sequence, and returns them in a new Sequence. In other words..

Seq = {1, 3, 5}
return = {(1+3)/2, (3+5)/2}
return = {2, 4}

Here's the implementation iteratively.
    private static Sequence<Integer> smooth(Sequence<Integer> s1) {
        Sequence<Integer> retSeq = s1.newInstance();
        Integer copy = null;
        for (int i : s1) {
            if (copy == null) {
                copy = i;
                continue;
            }
            retSeq.add(retSeq.length(), (copy + i) / 2);
            copy = i;
        }
        return retSeq;
    }


Here're the methods available.
Posted Image
Posted Image
I have two separate attempts at it, neither of them work. Posting the results.
        private static Sequence<Integer> smooth(Sequence<Integer> s1) {
        Sequence<Integer> retSeq = s1.newInstance();
        Sequence<Integer> copy = s1.newInstance();
        for (int i : s1) {
            copy.add(copy.length(), i);
        }
        if (s1.length() == 2) {
            int firstElement = copy.remove(0);
            int secondElement = copy.remove(0);
            p("2 elements left, removing: " + firstElement + " and "
                    + secondElement + ".");
            retSeq.add(retSeq.length(), (firstElement + secondElement) / 2);
        } else {
            int firstElement = s1.remove(0);
            int secondElement = copy.remove(1);
            p("Removing: " + firstElement + " and " + secondElement + ".");
            int firstSmoothed = (firstElement + secondElement) / 2;
            int smoothedNumber = smooth(s1).remove(0);
            p("Smoothed Number: " + smoothedNumber + ".");
            s1.add(0, firstElement);
            retSeq.add(0, firstSmoothed);
            retSeq.add(retSeq.length(), smoothedNumber);
        }
        p("Returning: " + retSeq.toString());
        return retSeq;
    }

Posted Image

    private static Sequence<Integer> smooth(Sequence<Integer> s1) {
        Sequence<Integer> retSeq = s1.newInstance();
        int tmp = 0;
        int tmp2 = 0;
        if (s1.length() == 2) {
            tmp = s1.remove(0);
            tmp2 = s1.remove(0);
            retSeq.add(retSeq.length(), (tmp + tmp2) / 2);
        } else {
            int lastDigit = s1.remove(s1.length() - 1);
            int nextDigit = s1.remove(s1.length() - 1);
            retSeq.add(retSeq.length(), (lastDigit + nextDigit) / 2);
            s1.add(s1.length(), nextDigit);
            int test = smooth(s1).remove(0);
            retSeq.add(retSeq.length(), test);
            s1.add(s1.length(), lastDigit);
        }
        return retSeq;
    }

Posted Image

Any help?

This forum doesn't allow images? Weird.

I also can't seem to edit my post. Sorry guys .~.

Is This A Good Question/Topic? 0
  • +

Replies To: Recursion with Sequences

#2 x68zeppelin80x  Icon User is offline

  • D.I.C Addict

Reputation: 130
  • View blog
  • Posts: 576
  • Joined: 07-March 09

Re: Recursion with Sequences

Posted 14 May 2014 - 05:12 PM

I don't understand exactly what you are asking, but is this similar to what you are expecting?

import java.util.Arrays;

public class Smooth {
	public static void main(String[] args) {
		print(smooth(new int[] { 1, 3, 5 }));
		print(smooth(new int[] { 1, 3, 5, 8, 2 }));
		print(smooth(new int[] { 1, 3, 5, 8, 2, 3, 6 }));
	}
	
	public static int[] smooth(int[] seq) {
		if (seq.length > 2) {
			int[] res = new int[seq.length - 1];
			for (int i = 0; i < seq.length - 1; i++) {
				res[i] = (seq[i] + seq[i+1]) / 2;
			}
			return smooth(res);
		}
		
		return seq;
	}
	
	public static void print(int... arr) {
		System.out.println(Arrays.toString(arr));
	}
}


Output:

[2, 4]
[4, 5]
[4, 3]

Was This Post Helpful? 0
  • +
  • -

#3 PreDominance  Icon User is offline

  • New D.I.C Head

Reputation: 5
  • View blog
  • Posts: 14
  • Joined: 14-May 14

Re: Recursion with Sequences

Posted 14 May 2014 - 05:35 PM

No sir, I apologize.

seq1 = {1, 3, 5, 7, 9, 11}
seq2 = smooth(seq1);
seq1 = {1, 3, 5, 7, 9, 11}
seq2 = {2, 4, 6, 8, 10}
Was This Post Helpful? 0
  • +
  • -

#4 x68zeppelin80x  Icon User is offline

  • D.I.C Addict

Reputation: 130
  • View blog
  • Posts: 576
  • Joined: 07-March 09

Re: Recursion with Sequences

Posted 14 May 2014 - 05:51 PM

View PostPreDominance, on 14 May 2014 - 08:35 PM, said:

No sir, I apologize.

seq1 = {1, 3, 5, 7, 9, 11}
seq2 = smooth(seq1);
seq1 = {1, 3, 5, 7, 9, 11}
seq2 = {2, 4, 6, 8, 10}


I thought you wanted it to be recursive? If not, then why not stop here:

public static int[] smooth(int[] seq) {
	if (seq.length > 2) {
		int[] res = new int[seq.length - 1];
		for (int i = 0; i < seq.length - 1; i++) {
			res[i] = (seq[i] + seq[i+1]) / 2;
		}
		//return smooth(res); <-- No more recursion.
		return res; // Only 1 iteration.
	}
	
	return seq;
}

Am I missing something?

This post has been edited by x68zeppelin80x: 14 May 2014 - 05:52 PM

Was This Post Helpful? 0
  • +
  • -

#5 PreDominance  Icon User is offline

  • New D.I.C Head

Reputation: 5
  • View blog
  • Posts: 14
  • Joined: 14-May 14

Re: Recursion with Sequences

Posted 14 May 2014 - 06:20 PM

You misunderstand me.

This needs to be done with a Sequence of type Integer (I gave the methods available). It needs to be recursive, and it needs to restore its parameter sequence.

The length of the returned sequence should be the length of the parameter - 1. If I have a sequence with 10, 20, 30, I should be returned a sequence of 15, 25, and the parameter sequence should still be 10, 20, 30.
Was This Post Helpful? 0
  • +
  • -

#6 x68zeppelin80x  Icon User is offline

  • D.I.C Addict

Reputation: 130
  • View blog
  • Posts: 576
  • Joined: 07-March 09

Re: Recursion with Sequences

Posted 15 May 2014 - 03:41 AM

View PostPreDominance, on 14 May 2014 - 09:20 PM, said:

This needs to be done with a Sequence of type Integer (I gave the methods available). It needs to be recursive, and it needs to restore its parameter sequence.


I guess I did not hit it enough, but could you provide the community with the source or a downloadable jar which contains the Sequence class. I have not hear of this being part of the Java standard or collections libraries. Is it essentially a linked list with a pointer to the original list?
Was This Post Helpful? 0
  • +
  • -

#7 PreDominance  Icon User is offline

  • New D.I.C Head

Reputation: 5
  • View blog
  • Posts: 14
  • Joined: 14-May 14

Re: Recursion with Sequences

Posted 15 May 2014 - 07:11 AM

I can post the API, but the Class itself isn't complicated. Here is the JAR file, but the functionality shouldn't be too different from an Arraylist. API.
Was This Post Helpful? 0
  • +
  • -

#8 x68zeppelin80x  Icon User is offline

  • D.I.C Addict

Reputation: 130
  • View blog
  • Posts: 576
  • Joined: 07-March 09

Re: Recursion with Sequences

Posted 15 May 2014 - 11:21 AM

Could this work? I could not use the jar where I am at, so I created a Sequence class from LinkedList. I assume that you would have to store a copy of the original.

import java.util.*;

class SequenceSmooth {
    public static void main (String[] args) {
		Sequence<Integer> seq = new Sequence(1, 3, 5, 7, 9, 11);
		System.out.println(smooth(seq));
        System.out.println(seq.getOriginal());
	}
	
	public static Sequence<Integer> smooth(Sequence<Integer> seq) {
		if (seq.size() > 2) {
			Sequence<Integer> res = new Sequence<Integer>();
			for (int i = 0; i < seq.size() - 1; i++) {
				res.add((seq.get(i) + seq.get(i+1)) / 2);
			}
			return res;
		}
		
		return seq;
	}
	
	static class Sequence<T> extends LinkedList<T> {
		private List<T> original;
		
		public Sequence() {
			this(new LinkedList());
		}
		
		public Sequence(Collection<? extends T> c) {
			super(c);
			
			original = new LinkedList(c);
		}
		
		public Sequence(T... sequence) {
			this(Arrays.asList(sequence));
		}
		
		public Sequence getOriginal() {
		    return new Sequence(original);
		}
	}
}

Was This Post Helpful? 0
  • +
  • -

#9 PreDominance  Icon User is offline

  • New D.I.C Head

Reputation: 5
  • View blog
  • Posts: 14
  • Joined: 14-May 14

Re: Recursion with Sequences

Posted 15 May 2014 - 11:23 AM

That's the iterative implementation, but you've got the right idea. It's similar to what I did above. Recursion for me is the harder part.
Was This Post Helpful? 0
  • +
  • -

#10 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5831
  • View blog
  • Posts: 12,683
  • Joined: 16-October 07

Re: Recursion with Sequences

Posted 16 May 2014 - 06:19 AM

Given the permissible methods, the only real option is to destroy the source. e.g.
private static Sequence<Integer> smoothRec(Sequence<Integer> s) {
    int n = s.remove(0); // pop the first
    int n2 = s.remove(0); // pop the next
    s.add(0, n2); // push the last one popped back on the stack
    // your code here



Of course, I suppose you could rebuild the source on the way back out...

Hope this helps.
Was This Post Helpful? 0
  • +
  • -

#11 PreDominance  Icon User is offline

  • New D.I.C Head

Reputation: 5
  • View blog
  • Posts: 14
  • Joined: 14-May 14

Re: Recursion with Sequences

Posted 16 May 2014 - 10:08 AM

It's definitely possible to make a copy and work with it, rather than destroying the source.


    private static Sequence<Integer> smooth(Sequence<Integer> s1) {
        Sequence<Integer> retSeq = s1.newInstance();
        Sequence<Integer> copy = s1.newInstance();
        for (int i : s1) {
            copy.add(copy.length(), i);
        }
    }

Was This Post Helpful? 0
  • +
  • -

#12 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5831
  • View blog
  • Posts: 12,683
  • Joined: 16-October 07

Re: Recursion with Sequences

Posted 16 May 2014 - 10:11 AM

What's you point? That's not a recursive function, is it?

You must answer the question: how does my recursive call know what step it's and and where it should stop.

I look forward to your non destructive recursive solution using the same method signature. Note, there is one, as I alluded to; only it's not immutable.

This post has been edited by baavgai: 16 May 2014 - 10:13 AM

Was This Post Helpful? 0
  • +
  • -

#13 PreDominance  Icon User is offline

  • New D.I.C Head

Reputation: 5
  • View blog
  • Posts: 14
  • Joined: 14-May 14

Re: Recursion with Sequences

Posted 16 May 2014 - 10:20 AM

That was supposed to be an example of how you could do it without touching the original Sequence, not the entire function itself.

If you look at my first post you'll see that I half-successfully implemented both of your suggestions already. The first method copies the Sequence, the second one modifies and restores it.

The recursion stops when the sequence has a length of one.
Was This Post Helpful? 0
  • +
  • -

#14 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5831
  • View blog
  • Posts: 12,683
  • Joined: 16-October 07

Re: Recursion with Sequences

Posted 16 May 2014 - 10:27 AM

Hmm... the second one from the original post looks close, only it's unclear why you start to pull from the back.

Do you have an example of a working destructive one?
Was This Post Helpful? 0
  • +
  • -

#15 PreDominance  Icon User is offline

  • New D.I.C Head

Reputation: 5
  • View blog
  • Posts: 14
  • Joined: 14-May 14

Re: Recursion with Sequences

Posted 16 May 2014 - 10:28 AM

I tried to pull in reverse because I was frustrated with the first one not working, and I wanted a clean start.

I can try to forgo restoration and get a destructive one working if you'd like. Give me a few.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2