• ### Popular Now

• 13
• 18
• 19
• 27
• 10

#### Archived

This topic is now archived and is closed to further replies.

# What the hell is this?

This topic is 5409 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm reading a book about algorithims in c++, and the first thing it has about recursion is this: http://www.geocities.com/drmulligan2000/untitled.jpg Which i cant figure out because dont you have enough information, do you? [edited by - Mulligan on May 28, 2003 8:56:07 PM]

##### Share on other sites
You can''t link directly to geocities.

##### Share on other sites
I''m not sure what you mean by "don''t have enough information." You have everything you need there to figure out every term greater than or equal to n = 1 (unless im not seeing something).

Fsub1 = 1
Fsub2 = 2
and after that, Fsubn = Fsub(n-1) + Fsub(n-2),
so Fsub3 = 3... (Fsub1 + Fsub2)
Fsub4 = 5 ... (Fsub2 + Fsub3)
etc.

It''s actually a pretty common algorithim to think of recursively, although a notoriously poor one to program that way.

##### Share on other sites
Oh, so youre saying that Fsubn is equal numerically to the ''n'' part? So what would Fsub3 be equal to? Am I actually looking for a number, or a drawn out formula?

##### Share on other sites
It''s the fibonacci sequence (though I believe there is a small error).

Basically you have a function, F, which has a parameter N, hence FN = F(N).

The "if n<=2 then n" means:

F(0) = 0
F(1) = 1
F(2) = 2 (technically this would not be the fibonacci sequence)

All other values of FN are defined as F(N-1)+F(N-2).

So F(2) = F(2-1)+F(2-2) = F(1)+F(0) = 1+0 = 1

and F(3)= F(3-1)+F(3-2) = F(2)+F(1) = 1+1 = 2

(well actually those are fib values, your values would be +1 since F(2) is defined as 2)

While this is not a good thing to program recursively, you can show a solution that is recursive and looks quite nice:
int F(int n){ if(n<=2) return (n) else return (F(n-1)+F(n-2));}

##### Share on other sites
Ahha, well thanks for the lengthy responses, this wll give me something to think about now. Thanks!

[edited by - Mulligan on May 28, 2003 9:12:42 PM]

##### Share on other sites
AH i get it, once again thanks! But to make sure, for F(7), did you get 21?

[edited by - Mulligan on May 28, 2003 9:25:13 PM]

##### Share on other sites
quote:
Original post by Mulligan
AH i get it, once again thanks! But to make sure, for F(7), did you get 21?

Let''s see...

n | 0 1 2 3 4 5 6 7 8
# | 0 1 1 2 3 5 8 13 21

No.

Qui fut tout, et qui ne fut rien

##### Share on other sites
Actually, I did.
Remember, it''s sort of a modified Fib sequence. F(2) is 2, not 1 like normal.

0 1 2 3 4 5 6 7
0 1 2 3 5 8 13 21

So yes, I got 21 for the 7th term as well.

Boo yaa grandma