Timeline for Find nth Fibonacci Number, using iteration and recursion
Current License: CC BY-SA 4.0
38 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Mar 7, 2020 at 13:26 | history | edited | forsvarir | CC BY-SA 4.0 |
Spelling correction
|
| S Mar 7, 2020 at 13:26 | history | suggested | Brijesh Kalkani | CC BY-SA 4.0 |
Spelling correction
|
| Mar 7, 2020 at 12:20 | review | Suggested edits | |||
| S Mar 7, 2020 at 13:26 | |||||
| Feb 29, 2020 at 12:00 | history | tweeted | twitter.com/StackCodeReview/status/1233723759925825536 | ||
| Feb 29, 2020 at 10:02 | answer | added | Sam Ginrich | timeline score: 1 | |
| Feb 28, 2020 at 3:05 | review | Close votes | |||
| Feb 29, 2020 at 3:10 | |||||
| Feb 24, 2020 at 1:03 | comment | added | President James K. Polk | @DavidConrad: Of course, but then that isn't an apples-to-apples comparison. If we go to multiprecision then we compare this to the O(log(n))-multiplies algorithm for computing exact integer Fibonacci number, and that would again be apples-to-apples. | |
| Feb 22, 2020 at 23:42 | answer | added | Sam Ginrich | timeline score: 4 | |
| Feb 21, 2020 at 20:49 | comment | added | Cubic |
@mypronounismonicareinstate Also I don't like calling it the recursive version. You can write a recursive version of fib that's pretty fast (as in, fast enough that stack space / number range limits are going to become an issue long before performance will) (although it'll still be a bit slower than the iterative version unless your compiler is doing tail call elimination).
|
|
| Feb 21, 2020 at 15:25 | history | edited | Toby Speight | CC BY-SA 4.0 |
deleted 78 characters in body; edited title
|
| Feb 21, 2020 at 8:29 | comment | added | rcgldr | "Why do most people (on the internet) recommend using recursion" - It depends on the purpose. Take the case of merge sort. For educational purposes, recursive top down merge sort is the most popular, but almost all stable sorts as implemented in libraries use some variation of a hybrid insertion sort and bottom up merge sort, such as timsort. | |
| Feb 21, 2020 at 2:33 | answer | added | James Dunlap | timeline score: 1 | |
| Feb 20, 2020 at 22:19 | comment | added | David Conrad | @PresidentJamesMoveonPolk The closed form solution can work for much larger values by using a multiprecision math library like gmplib.org | |
| Feb 20, 2020 at 14:56 | comment | added | David Peterson | @user207421 I dont know if these count as evidence but here they are: link and this one link | |
| Feb 20, 2020 at 14:49 | history | edited | David Peterson | CC BY-SA 4.0 |
Explaining some of the things
|
| Feb 20, 2020 at 14:19 | comment | added | the default. | I'm completely not seeing the explanation of why the recursive method is slow in the answers: the reason is that it pretty much builds the Fibonacci number by adding lots of ones together (and therefore will add an exponentially growing number of them) | |
| Feb 20, 2020 at 11:26 | comment | added | user207421 | Do 'most people (on the internet) recommend using recursion'? Really? I doubt this is true. Evidence please. | |
| Feb 20, 2020 at 8:37 | answer | added | dumetrulo | timeline score: 3 | |
| Feb 20, 2020 at 6:51 | answer | added | Sid | timeline score: 2 | |
| Feb 20, 2020 at 0:59 | comment | added | President James K. Polk | @canton7: The closed form solution will be wrong starting at Fib(70), presuming binary64 doubles are used. The iterative solution will give a correct answer with 64-bit integer arithmetic up to Fib(92) inclusive. | |
| Feb 19, 2020 at 22:02 | answer | added | Sam Ginrich | timeline score: 6 | |
| Feb 19, 2020 at 20:17 | vote | accept | David Peterson | ||
| Feb 19, 2020 at 18:49 | answer | added | David Foerster | timeline score: 7 | |
| Feb 19, 2020 at 17:59 | comment | added | FreezePhoenix | Note: It is possible find any fibonacci number in O(log n) time, or, in some cases, O(1) time. | |
| Feb 19, 2020 at 13:30 | comment | added | pacmaninbw♦ | Congratulations on your first nice question badge. As an experiment, you might want to try putting both of these algorithms into the same main and time each function call and report back the elapsed time. | |
| Feb 19, 2020 at 12:52 | comment | added | Rupe | What @canton7 says. I sometimes use this as to kick off an wide-ranging interview discussion. Present the candidate with a recursive version, get them to explain what it does, then off you go into discussions of "good/bad" metrics, performance, iterative version, look-up tables, and eventually the fact that there's a closed form (the best, even if they don't know about that, on seeing that it's about fibonnacci, quickly ask if they can google it and come up with the closed form). With C++ there's also a compile-time solution as you can do it with templates. | |
| Feb 19, 2020 at 12:40 | comment | added | canton7 | "Iteration or recursion" -- neither, there's a closed form solution | |
| Feb 19, 2020 at 9:34 | answer | added | rcgldr | timeline score: 5 | |
| Feb 19, 2020 at 6:29 | comment | added | Loki Astari |
The using namespace std; is not about speed. It is about maintainability. It is a bad habit that in the long run will make your code hard to maintain (and cause bugs (see linked article). That is why it is considered bad practice. Why is “using namespace std;” considered bad practice?
|
|
| Feb 19, 2020 at 6:20 | comment | added | Loki Astari | The recursive version is trivial to see you have done it correctly. The iterative version takes a bit of thought (not much but some). But you have stopped on the iterative version as if that is the correct answer. There is so much more to do. This is why I like this as an interview question (as a proxy for thinking as fib() solutions are obvious). But you can make candidates think about all the other issues. | |
| Feb 19, 2020 at 3:34 | history | became hot network question | |||
| Feb 18, 2020 at 22:53 | answer | added | Eric Lippert | timeline score: 41 | |
| Feb 18, 2020 at 21:42 | answer | added | Sriv | timeline score: 3 | |
| Feb 18, 2020 at 19:40 | review | Close votes | |||
| Feb 19, 2020 at 13:55 | |||||
| Feb 18, 2020 at 19:36 | answer | added | pacmaninbw♦ | timeline score: 5 | |
| Feb 18, 2020 at 19:29 | history | edited | pacmaninbw♦ |
edited tags
|
|
| Feb 18, 2020 at 19:27 | comment | added | pacmaninbw♦ |
For most reviewers on the site, it is easier to understand if you done have the using namespace std; statement.
|
|
| Feb 18, 2020 at 19:20 | history | asked | David Peterson | CC BY-SA 4.0 |