Recursion with Sequences

  • (2 Pages)
  • +
  • 1
  • 2

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

#16 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5832
  • View blog
  • Posts: 12,683
  • 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


Was This Post Helpful? 0
  • +
  • -

#17 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: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);
            s1.add(0, second);
            s1.add(0, first);
        } else if (s1.length() > 2) {
            int first = s1.remove(0);
            int second = s1.remove(0);
            retSeq.add(retSeq.length(), (first + second) / 2);
            s1.add(0, second);
            for (int i : smooth(s1)) {
                retSeq.add(retSeq.length(), i);
            }
            s1.add(0, first);
        }
        return retSeq;
    }

    public static void main(String[] args) {
        SimpleReader in = new SimpleReader1L();
        SimpleWriter out = new SimpleWriter1L();
        Sequence<Integer> seq1 = new Sequence1L<Integer>();
        seq1.add(seq1.length(), 1);
        seq1.add(seq1.length(), 3);
        seq1.add(seq1.length(), 5);
        seq1.add(seq1.length(), 7);
        seq1.add(seq1.length(), 9);
        seq1.add(seq1.length(), 11);
        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 

Was This Post Helpful? 0
  • +
  • -

#18 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5832
  • View blog
  • Posts: 12,683
  • 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.
Was This Post Helpful? 1
  • +
  • -

#19 x68zeppelin80x  Icon User is offline

  • D.I.C Addict

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

Re: Recursion with Sequences

Posted 16 May 2014 - 03:34 PM

View Postbaavgai, 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

Was This Post Helpful? 0
  • +
  • -

#20 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5832
  • View blog
  • Posts: 12,683
  • 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.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2