Archived

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

What the hell is this?

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites