New answers tagged

1

Evaluating Asymptotic Complexity e.g. with gmp library, shows that rcgldr's algorithm, implementing efficient matrix powers with O(log(n)) mutlipications, has best performance among presented algorithms. Below compared for n in range 0 .... 647028207 Straight Iteration, n steps, takes O(n^1.60) time. "Golden Ratio", i.e. above called the "Binet's Formula" ...


1

The equation given by Binet: fib[n] = (phi^n - (-phi)^(-n)) / sqrt(5) where phi=(1+sqrt(5))/2 will give an accurate answer (unlike the answer above of fib [n] = phi^n / sqrt(5) + 1/2), which breaks down at values of n greater than 70). Since you can calculate it directly, iteration and recursion are unnecessary.


3

While this thread already has many answers, one of which accepted, I would like to point out that the (naïve) recursive solution presented by OP has a much worse complexity than the iterative version. However, it is perfectly possible to split up the problem into a main function to be called by the user, and an internal helper function doing the work ...


2

The debate around recursive vs iterative code is endless. Some say that recursive code is more "compact" and simpler to understand.. In both cases (recursion or iteration) there will be some 'load' on the system when the value of n i.e. fib(n) grows large.Thus fib(5) will be calculated instantly but fib(40) will show up after a slight delay. Of course your ...


5

Neither nor! David Foerster's __fibonacci_impl has a matrix representation, where the matrix can be brought into a diagonal shape, evaluating to a difference of two exponential functions, where the absolute value of the latter one is less than one and so may be replaced by a rounding operator. const double sqr5 = sqrt(5); const double phi = 0.5 * (sqr5+1)...


3

As other answers state, your iterative algorithm outperforms your recursive algorithm because the former remembers previous intermediate results (or at least one such result) while the latter doesn’t. Of course, one can write recursive algorithms that remember previous results. For Fibonacci numbers that’s simple enough since you only need to remember one ...


3

Is there a better way than these two methods?And are these methods complex? There are better methods, and although not that complex, few people would be able to develop such methods (such as Lucas sequence relations) on their own without relying on some reference. For the recursive version shown in the question, the number of instances (calls) made to ...


33

Why do most people (on the internet) recommend using recursion because it's simpler and easier to write the program? Logically I thought that we should write it in a way that is fast and simple. This is a perceptive question. I wrote an article about exactly this topic in 2004, which you can read here: https://docs.microsoft.com/en-us/archive/blogs/...


3

By using that iterative solution, you are indirectly using Dynamic Programming (DP) Answer for question number 1: Recursion might be faster in some cases. For example, let's say you have a 2d road of size n * m. There are blockages in the road, so you can't pass through them. The objective is to check if there exists any path from the top-left corner to ...


4

In the recursive version of the code you don't need the function prototype unsigned long long fibonacci(unsigned long long n);. As you mentioned you shouldn't have the using namespace std; statement in the code. We can't answer Why do most people (on the internet) recommend using recursion because it's simpler and easier to write the program?(well ...


8

Avoid using namespace std It's a bad idea to import large namespaces such as std into the global namespace, and it could possibly even change the meaning of your code when a later standard adds new identifiers. Reserve using namespace for those few namespaces specifically designed to be used that way (notably std::literals). Use const appropriately We ...


3

String parsing You are right that C++ slightly lacks some convenient features for string parsing. If you were not trying to count lines as well as find words, then a single while loop with: inFile >> s; would have sufficed, because streaming will terminate on whitespace by default. But because you want to count lines, you need the 2 loops and ...


3

Clean and readable code! Nice work. Here's some nitpicks. swap_together template<class... Its> void swap_together(size_t i, size_t j, Its... its) { using std::swap; int dummy[] = { [&](){ auto it = its + i; auto jt = its + j; using std::swap; swap(*it, *jt); return 0; ...


Top 50 recent answers are included