# How do you define a sequence of numbers recursively?

• (2 Pages)
• 1
• 2

## 28 Replies - 2014 Views - Last Post: 21 May 2012 - 06:37 AM

### #16 TechSyndrome

Reputation: 3
• Posts: 135
• Joined: 06-May 12

## Re: How do you define a sequence of numbers recursively?

Posted 20 May 2012 - 01:17 PM

I get it! Pn-3 is P minus 3 index which is P0! Then Pn-1 is P minus index 1 which equals P2! So the first few indexes have already been defined, and all we are doing is subtracting the index!

This post has been edited by TechSyndrome: 20 May 2012 - 01:17 PM

### #17 sepp2k

• D.I.C Lover

Reputation: 1690
• Posts: 2,553
• Joined: 21-June 11

## Re: How do you define a sequence of numbers recursively?

Posted 20 May 2012 - 01:17 PM

Okay, so let's say we're looking for P6. We know we need to use the rule "Pn = (Pn - 3 * Pn-1) + 1". The way to use that rule to find P6 is to replace each occurrence of n with 6. So we get the rule:

P6 = (P6 - 3 * P6-1) + 1

Now we 6-3 and 6-1 are easily calculated, so we get:

P6 = (P3 * P5) + 1

Now we only need to know the values of P3 and P5. If we already calculated those, we can just insert them and we're done. If we haven't calculated them yet, we need to apply the rule again, this time replacing n with 5 (and then after that with 3), instead of 6.

### #18 TechSyndrome

Reputation: 3
• Posts: 135
• Joined: 06-May 12

## Re: How do you define a sequence of numbers recursively?

Posted 20 May 2012 - 01:28 PM

sepp2k, on 20 May 2012 - 01:17 PM, said:

Okay, so let's say we're looking for P6. We know we need to use the rule "Pn = (Pn - 3 * Pn-1) + 1". The way to use that rule to find P6 is to replace each occurrence of n with 6. So we get the rule:

P6 = (P6 - 3 * P6-1) + 1

Now we 6-3 and 6-1 are easily calculated, so we get:

P6 = (P3 * P5) + 1

Now we only need to know the values of P3 and P5. If we already calculated those, we can just insert them and we're done. If we haven't calculated them yet, we need to apply the rule again, this time replacing n with 5 (and then after that with 3), instead of 6.

I'm writing this out with a pen right now to make sure I understand it fully.

### #19 TechSyndrome

Reputation: 3
• Posts: 135
• Joined: 06-May 12

## Re: How do you define a sequence of numbers recursively?

Posted 20 May 2012 - 01:34 PM

TechSyndrome, on 20 May 2012 - 01:28 PM, said:

sepp2k, on 20 May 2012 - 01:17 PM, said:

Okay, so let's say we're looking for P6. We know we need to use the rule "Pn = (Pn - 3 * Pn-1) + 1". The way to use that rule to find P6 is to replace each occurrence of n with 6. So we get the rule:

P6 = (P6 - 3 * P6-1) + 1

Now we 6-3 and 6-1 are easily calculated, so we get:

P6 = (P3 * P5) + 1

Now we only need to know the values of P3 and P5. If we already calculated those, we can just insert them and we're done. If we haven't calculated them yet, we need to apply the rule again, this time replacing n with 5 (and then after that with 3), instead of 6.

I'm writing this out with a pen right now to make sure I understand it fully.

I'm sorry if I'm going around in circles, but how does P3 in "P6 = (P3 * P5) + 1" represent the value 2? We know that P0, P1, P2 is equal to 1, but P3 hasn't actually been given a value yet?

This post has been edited by TechSyndrome: 20 May 2012 - 01:43 PM

### #20 TechSyndrome

Reputation: 3
• Posts: 135
• Joined: 06-May 12

## Re: How do you define a sequence of numbers recursively?

Posted 20 May 2012 - 01:39 PM

Please refer me back if you have already explained this to me.

### #21 macosxnerd101

• Self-Trained Economist

Reputation: 9032
• Posts: 33,508
• Joined: 27-December 08

## Re: How do you define a sequence of numbers recursively?

Posted 20 May 2012 - 01:42 PM

P3 is equal to the value of P0 * P2 + 1, which evaluates to 1 * 1 + 1, which is 2.

### #22 TechSyndrome

Reputation: 3
• Posts: 135
• Joined: 06-May 12

## Re: How do you define a sequence of numbers recursively?

Posted 20 May 2012 - 01:44 PM

macosxnerd101, on 20 May 2012 - 01:42 PM, said:

P3 is equal to the value of P0 * P2 + 1, which evaluates to 1 * 1 + 1, which is 2.

Oh right, I thought the gentleman who was helping was giving me an alternative method to work backwards. Thanks.

### #23 sepp2k

• D.I.C Lover

Reputation: 1690
• Posts: 2,553
• Joined: 21-June 11

## Re: How do you define a sequence of numbers recursively?

Posted 20 May 2012 - 01:45 PM

TechSyndrome, on 20 May 2012 - 10:34 PM, said:

I'm sorry if I'm going around in circles, but how does P3 represent the value 2? We know that P0, P1, P2 is equal to 1, but P3 hasn't actually been given a value yet?

We calculate P3 the same way we do P6, i.e. by taking the rule "Pn = (Pn - 3 * Pn-1) + 1" and replacing n with 3, so we get:

P3 = (P3 - 3 * P3-1) + 1

, which is:

P3 = (P0 * P2) + 1

Since we already know P0 and P2 this becomes:

P3 = (1 * 1) + 1

, which is 2.

### #24 macosxnerd101

• Self-Trained Economist

Reputation: 9032
• Posts: 33,508
• Joined: 27-December 08

## Re: How do you define a sequence of numbers recursively?

Posted 20 May 2012 - 01:46 PM

Look at your recurrence and plug in the values. P0, P1 and P2 are your base cases. Since P3 is the first term defined by the recurrence relation, that's the first term that will utilize the base cases.

### #25 TechSyndrome

Reputation: 3
• Posts: 135
• Joined: 06-May 12

## Re: How do you define a sequence of numbers recursively?

Posted 20 May 2012 - 01:51 PM

OMG, OMG! I've figured it out! I'm so excited, I'm gonna display how I did it and you guys please confirm! Thank you for your help!

So basically I worked backwards as #23 sepp2k explained. I was looking for P6, so I replaced all occurrences of n in the fourth rule with 6. The key was to do the calculation AFTERWARDS, but to replace all occurrences of n in the fourth rule FIRST.

### #26 sepp2k

• D.I.C Lover

Reputation: 1690
• Posts: 2,553
• Joined: 21-June 11

## Re: How do you define a sequence of numbers recursively?

Posted 20 May 2012 - 01:55 PM

TechSyndrome, on 20 May 2012 - 10:44 PM, said:

I thought the gentleman who was helping was giving me an alternative method to work backwards. Thanks.

Oh, I am. To make this more clear, let's start with P6 and go all the way down to the bottom:

P6 = (P6 - 3 * P6-1) + 1

Now 6-3 and 6-1 are easily calculated, so we get:

P6 = (P3 * P5) + 1

Now we only need to know the values of P3 and P5. So let's start with P5:

P5 = (P5 - 3 * P5-1) + 1
= (P2 * P4) + 1

We already have P2 because that's one of the base cases. We still need P4, so let's calculate that:

P4 = (P4 - 3 * P4-1) + 1
= (P1 * P3) + 1

So now P3:

P3 = (P0 * P2) + 1

We know P0 and P2, so we get:

P3 = 2

So now we can go up again to P4:

P4 = (P1 * P3) + 1
= (1*2)+1 = 3

And now P5:

P5 = (P2 * P4) + 1
= (1*3)+1 = 4

And now P6:

P6 = (P3 * P5) + 1
= (2*4)+1 = 9

What we did here basically is to start at the top, then go all the way down to the bottom and then go up again. As I said earlier, this has no advantage over simply starting at the bottom and then going up in this case.

However in cases where we don't need to calculate all the preceding elements to calculate the next one, this approach can save needless calculations.

In fact there are even sequences where an element can depend on other elements that come after it. In those cases the bottom-up approach doesn't work and you actually need to use this approach.

### #27 macosxnerd101

• Self-Trained Economist

Reputation: 9032
• Posts: 33,508
• Joined: 27-December 08

## Re: How do you define a sequence of numbers recursively?

Posted 20 May 2012 - 01:57 PM

Also, I'm going to move this to the Computer Science forum since it isn't a Java question.

### #28 TechSyndrome

Reputation: 3
• Posts: 135
• Joined: 06-May 12

## Re: How do you define a sequence of numbers recursively?

Posted 20 May 2012 - 02:02 PM

sepp2k, on 20 May 2012 - 01:55 PM, said:

TechSyndrome, on 20 May 2012 - 10:44 PM, said:

I thought the gentleman who was helping was giving me an alternative method to work backwards. Thanks.

Oh, I am. To make this more clear, let's start with P6 and go all the way down to the bottom:

P6 = (P6 - 3 * P6-1) + 1

Now 6-3 and 6-1 are easily calculated, so we get:

P6 = (P3 * P5) + 1

Now we only need to know the values of P3 and P5. So let's start with P5:

P5 = (P5 - 3 * P5-1) + 1
= (P2 * P4) + 1

We already have P2 because that's one of the base cases. We still need P4, so let's calculate that:

P4 = (P4 - 3 * P4-1) + 1
= (P1 * P3) + 1

So now P3:

P3 = (P0 * P2) + 1

We know P0 and P2, so we get:

P3 = 2

So now we can go up again to P4:

P4 = (P1 * P3) + 1
= (1*2)+1 = 3

And now P5:

P5 = (P2 * P4) + 1
= (1*3)+1 = 4

And now P6:

P6 = (P3 * P5) + 1
= (2*4)+1 = 9

What we did here basically is to start at the top, then go all the way down to the bottom and then go up again. As I said earlier, this has no advantage over simply starting at the bottom and then going up in this case.

However in cases where we don't need to calculate all the preceding elements to calculate the next one, this approach can save needless calculations.

In fact there are even sequences where an element can depend on other elements that come after it. In those cases the bottom-up approach doesn't work and you actually need to use this approach.

I just used your bottom up approach in a different question and it worked!!! THANK YOU SO MUCH! I'm gonna read what you've just written right now...I'm so afraid I'm gonna forget this stuff. Amazing that just 1 hour ago I was depressed at not understanding any of this!

macosxnerd101, on 20 May 2012 - 01:57 PM, said:

Also, I'm going to move this to the Computer Science forum since it isn't a Java question.

The second part of this question is related to Java. This is all part of Data Structures and Algorithms in Java. Does that count?

### #29 jon.kiparsky

• Pancakes!

Reputation: 5422
• Posts: 8,717
• Joined: 19-March 11

## Re: How do you define a sequence of numbers recursively?

Posted 21 May 2012 - 06:37 AM

The material in Algorithms and Data Structures applies to programming generally, not to any particular language. A linked list is a linked list, no matter what syntax you use to define it for the computer.