# Recursion with Sequences

• (2 Pages)
• 1
• 2

## 19 Replies - 1640 Views - Last Post: 16 May 2014 - 04:47 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=346952&amp;s=4065e7e6471c54bebf24b9ef8531662a&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 PreDominance

Reputation: 5
• 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.

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) {
}
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 + ".");
}
p("Returning: " + retSeq.toString());
return retSeq;
}
```

```    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);
int test = smooth(s1).remove(0);
}
return retSeq;
}
```

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

Reputation: 130
• 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]

### #3 PreDominance

Reputation: 5
• 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}

### #4 x68zeppelin80x

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

## Re: Recursion with Sequences

Posted 14 May 2014 - 05:51 PM

PreDominance, 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

### #5 PreDominance

Reputation: 5
• 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.

### #6 x68zeppelin80x

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

## Re: Recursion with Sequences

Posted 15 May 2014 - 03:41 AM

PreDominance, 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?

### #7 PreDominance

Reputation: 5
• 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.

### #8 x68zeppelin80x

Reputation: 130
• 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++) {
}
return res;
}

return seq;
}

static class Sequence<T> extends LinkedList<T> {
private List<T> original;

public Sequence() {
}

public Sequence(Collection<? extends T> c) {
super(c);

}

public Sequence(T... sequence) {
this(Arrays.asList(sequence));
}

public Sequence getOriginal() {
return new Sequence(original);
}
}
}
```

### #9 PreDominance

Reputation: 5
• 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.

### #10 baavgai

• Dreaming Coder

Reputation: 6578
• Posts: 13,908
• 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

```

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

Hope this helps.

### #11 PreDominance

Reputation: 5
• 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) {
}
}
```

### #12 baavgai

• Dreaming Coder

Reputation: 6578
• Posts: 13,908
• 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

### #13 PreDominance

Reputation: 5
• 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.

### #14 baavgai

• Dreaming Coder

Reputation: 6578
• Posts: 13,908
• 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?

### #15 PreDominance

Reputation: 5
• 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.