Recursion with Sequences

• (2 Pages)
• 1
• 2

19 Replies - 1356 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=fbd5cfc14afe7fab86a0a7a29da52af4&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#16 baavgai

• Dreaming Coder

Reputation: 6380
• Posts: 13,630
• Joined: 16-October 07

Re: Recursion with Sequences

Posted 16 May 2014 - 10:44 AM

Ok, here's the trick:

Consider your data set: { 1, 3, 5 }

Think of it as a stack. You pop, pop, push, call, push. At the end of this, the state is actually restored: the pops and pushes balance.

The process goes like:
f(s={1,3,5})
n1 = pop(s): n1 = 1 : s = {3,5}
n2 = pop(s): n2 = 3 : s = {5}
push(n2, s) : s = {3,5}
f(s={3,5})
n1 = pop(s): n1 = 3 : s = {5}
n2 = pop(s): n2 = 5 : s = {}
push(n2, s) : s = {5}
result = {}
result = {4}
push(n1, s) : s = {3,5}
return result
result = {4}
push(n1, s) : s = {1,3,5}
return result

#17 PreDominance

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

Re: Recursion with Sequences

Posted 16 May 2014 - 10:56 AM

I just got it

I knew how to restore it. The problem was with my logic within the recursion. The returning sequence contained two elements, but you can see I only make one call to smooth(s1).remove(0), where the Sequence returned by smooth actually had 2 values.

private static Sequence<Integer> smooth(Sequence<Integer> s1) {
Sequence<Integer> retSeq = s1.newInstance();
if (s1.length() == 2) {
int first = s1.remove(0);
int second = s1.remove(0);
retSeq.add(0, (first + second) / 2);
} else if (s1.length() > 2) {
int first = s1.remove(0);
int second = s1.remove(0);
retSeq.add(retSeq.length(), (first + second) / 2);
for (int i : smooth(s1)) {
}
}
return retSeq;
}

public static void main(String[] args) {
SimpleWriter out = new SimpleWriter1L();
Sequence<Integer> seq1 = new Sequence1L<Integer>();
Sequence<Integer> seq2 = smooth(seq1);
out.println("Printing Smoothed Sequence..");
for (int i : seq2) {
System.out.println(i);
}
out.print("Testing Restoration: ");
for (int i : seq1) {
out.print(i + " ");
}
in.close();
out.close();
}

Printing Smoothed Sequence..
2
4
6
8
10
Testing Restoration: 1 3 5 7 9 11

#18 baavgai

• Dreaming Coder

Reputation: 6380
• Posts: 13,630
• Joined: 16-October 07

Re: Recursion with Sequences

Posted 16 May 2014 - 11:37 AM

Looks functional. All those instances, though. And a loop?

Since you now have a solution, to be fair, here's mine:
private static Sequence<Integer> smooth(Sequence<Integer> s) {
if (s.length()<2) {
return s.newInstance(); // this is the only return instance we'll ever create
} else {
int n = s.remove(0); // pop
int n2 = s.remove(0); // pop
s.add(0, n2); // push the last pop back
Sequence<Integer> result = smooth(s); // all self, now one number taken from top
result.add(0, (n + n2)/2); // do the math
s.add(0, n); // push the other number back, so we balance
return result; // return the result
}
}

Hope this helps.

#19 x68zeppelin80x

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

Re: Recursion with Sequences

Posted 16 May 2014 - 03:34 PM

baavgai, on 16 May 2014 - 02:37 PM, said:

Looks functional. All those instances, though. And a loop?

I noticed that too, PreDominance wants to solve this using recursion, but his last solution appears iterative.

Well, I know that this is the Java forum, but python can be excellent for pseudocode. I have written 4 separate methods that do the same thing. I have not run them thought performance tests (timeit), but I will in the near future. You can try out the python demo here is you like.

Of course, you cannot nest functions, but you can create a public (helper) method which will call a private method which will handle the recursion.

I find that it helps. if you are interested in python, to template and prototype all your logic in a typeless language, then port it back into Java.
''' Create another list. (iterative) '''
def interpolate1(l):
if l is not list: l = list(l)
if len(l) > 2:
for i in range(len(l)-1):
l[i] = (l[i]+l[i+1])/2
return l[:-1]

''' Create another list. (recursive) '''
def interpolate2(l):
def execute(l, r, i):
if len(r) < len(l) - 1:
r.append((l[i]+l[i+1])/2)
return execute(l, r, i+1)
return r
if len(l) > 2:
return execute(l, list(), 0)
return l

''' Edit copy list in place. (recursive) '''
def interpolate3(l):
def execute(l, i):
l[i] = (l[i]+l[i+1])/2
if i < len(l)-2:
return execute(l, i+1)
return l
if len(l) > 2:
return execute(list(l), 0)[:-1]
return l

''' baavgai's solution. '''
def interpolate4(l):
if l is not list: l = list(l)
if (len(l) < 2):
return l[:-1] # this is the only return instance we'll ever create
else:
n = l.pop(0) # pop
n2 = l.pop(0) # pop
l.insert(0, n2) # push the last pop back
r = interpolate4(l) # all self, now one number taken from top
r.insert(0, (n+n2)/2) # do the math
l.insert(0, n) # push the other number back, so we balance
return r # return the result

l = (0, 1, 2, 4, 8, 16, 32, 64, 128)

print interpolate1(l) # prints [0, 1, 3, 6, 12, 24, 48, 96]
print interpolate2(l) # prints [0, 1, 3, 6, 12, 24, 48, 96]
print interpolate3(l) # prints [0, 1, 3, 6, 12, 24, 48, 96]
print interpolate4(l) # prints [0, 1, 3, 6, 12, 24, 48, 96]

This post has been edited by x68zeppelin80x: 16 May 2014 - 03:39 PM

#20 baavgai

• Dreaming Coder

Reputation: 6380
• Posts: 13,630
• Joined: 16-October 07

Re: Recursion with Sequences

Posted 16 May 2014 - 04:47 PM

Ok, if we're switching to python, I'd go with something like:
def smooth(xs):
if len(xs)<2:
return []
else:
result = [ (xs[0] + xs[1] ) / 2 ]
result.extend(smooth(xs[1:]))
return result

You could also write is recursively in F# as:
let rec smooth = function
| x::y::xs -> ((x+y)/2) :: smooth (y::xs)
| _-> []

However, I don't really see the point.

In the context of the OP, they have a Java collection class with limited available methods and THAT is the problem domain. Solving the program in languages more suited to it, using more flexible structures, while entertaining, doesn't seem overly helpful.