Programming Forums

Programming Forums (http://www.programmingforums.org/forumindex.php)
-   Java (http://www.programmingforums.org/forum17.html)
-   -   Recursion to compute sequences. (http://www.programmingforums.org/showthread.php?t=15379)

emdiesse Mar 9th, 2008 7:17 PM
Recursion to compute sequences.
 
Hello. I am attempting to use recursion to output the sequence of numbers 2, 3, 7, 13, 27, 53, ...

:
public class TDSeq {
  private static int printSequence(int F, int k) {
      if(k ==1) return 2;
      if(k ==2) return 3;
      F = printSequence(F, k-1)  + (2*printSequence(F, k-2));
      System.out.print(F + ", ");
      return F;   
  }
   
  public static void main(String[] args) {
      int k = 8;
      int F = 3;
      printSequence(F, k);
  } 
}

Now this give a horrible output:
7, 13, 7, 27, 7, 13, 53, 7, 13, 7, 27, 107, 7, 13, 7, 27, 7, 13, 53, 213,

No where near the aim of:

2, 3, 7, 13, 27, 53, ...

Now I really can't get my head around this, however I would really like to learn how to use recursion effectively.

Any one got any help or advice they can offer?

Ooble Mar 9th, 2008 10:04 PM
Re: Recursion to compute sequences.
 
You have two main problems. One is that you print the numbers right after you generate them, not when you've finished the recursion, and the other is that you never print 2 or 3.

Here's some pseudocode (actually Python code, but they're essentially the same thing) that'll do it, though it's not efficient. You'd need to work on some kind of caching for that.

:
def sequence(k):
    if k == 1:
        return 2
    elif k == 2:
        return 3
    else:
        return sequence(k - 1) + 2 * sequence(k - 2)
   
def main():
    for i in xrange(1, 10):
        print sequence(i)

emdiesse Mar 10th, 2008 7:54 AM
Re: Recursion to compute sequences.
 
Quote:
Originally Posted by Ooble (Post 142272)
You have two main problems. One is that you print the numbers right after you generate them, not when you've finished the recursion, and the other is that you never print 2 or 3.

Here's some pseudocode (actually Python code, but they're essentially the same thing) that'll do it, though it's not efficient. You'd need to work on some kind of caching for that.

:
def sequence(k):
    if k == 1:
        return 2
    elif k == 2:
        return 3
    else:
        return sequence(k - 1) + 2 * sequence(k - 2)
   
def main():
    for i in xrange(1, 10):
        print sequence(i)
Ahah. That makes alot more sense to me now. I don't know why i had an F parametre in the last one, lol. If i didn't want an external loop is there a way to place it inside or is that bad programming?

:
public class TDSeq {
  private static int F = 0;
 
  private static void printSequence(int i) {
        for(int k=1;k<=i;k++){            //can i place this in calcSequence?
            System.out.print(calcSequence(k) + ","); 
        }
  }
 
  private static int calcSequence(int k) {
      if(k ==1) return 2;
      else if(k ==2){ return 3;}
      else return ( calcSequence(k-1)  + (2*calcSequence(k-2)) );
  }
   
  public static void main(String[] args) {
      int i = 7;
        printSequence(i);
  } 
}

Ooble Mar 10th, 2008 2:25 PM
Re: Recursion to compute sequences.
 
Thinking about it, it doesn't make much sense. The numbers aren't parsed through in order, so they wouldn't be printed in order. I can't think of a way to do it right now... hopefully it'll come to me soon.

OpenLoop Mar 10th, 2008 6:18 PM
Re: Recursion to compute sequences.
 
try this:
:
  1. def myseq(k, run):
  2.     if k >= 500:
  3.         return 0
  4.     print k
  5.     if run == 1:
  6.         return myseq((2 * k) + 1, 0)
  7.     else:
  8.         return myseq((2 * k) - 1, 1)
  9.  
  10. def main():
  11.     myseq(2, 0) 
  12.  
  13. main()


All times are GMT -5. The time now is 4:20 AM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC