What the hell is this?
Author
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]
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.
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.
Author
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?
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:
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));}
Author
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]
[edited by - Mulligan on May 28, 2003 9:12:42 PM]
Author
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]
[edited by - Mulligan on May 28, 2003 9:25:13 PM]
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
Invader''s Realm
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement