New answers tagged

4

Neither of your implementations is "advantageous" over other because both of them are C-style, unidiomatic C++ code — they are really C code with a handful of C++ additions. Moreover, they share many errors. This review will (hopefully) help you convert your code to C++ style and fix these errors. Formatting The indentation of the first ...


3

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 question already has many answers, one of which is 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)...


6

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 ...


4

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 ...


34

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 ...


5

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 ...


7

A few general tips: Have a function name that indicates what the function does. If it's hard to come up with a name that describes the function's purpose (e.g. because it does totally different things depending on what argument you pass it), it's a clue that the function needs to be broken up into multiple functions with clearer purposes. It looks like ...


0

Always option 1. That way it will correctly use bold in cases when the browser doesn't support or can't download the fonts.


5

If you only need to split collection into 2 pieces by a certain criterion, then there's a built-in collector to achieve this: final List<Integer> numbers = asList(1, 2, 3, 4, 5); final Map<Boolean, List<Integer>> lists = numbers.stream().collect(Collectors.partitioningBy(n -> n % 2 == 0)); System.out.println(lists.get(true)); System....


3

CRTP Caveat: It's not quite clear what the <a> template parameter is doing/ For my understanding your option1 defeats the purpose of CRTP. That is, if it's even trying to do CRTP. It's not clear due to the template parameter <a> which appears to have no purpose. Fact is, Option1 It's working just like normal polymorphism, see below. In the ...


Top 50 recent answers are included