Archived

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

Mulligan

What the hell is this?

Recommended Posts

Mulligan    378
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
Tibre    175
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
Mulligan    378
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
Michalson    1657
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
Mulligan    378
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
Tibre    175
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