
SCJP 1.4  SCJP 6  SCWCD 5  OCEEJBD 6  OCEJPAD 6
How To Ask Questions How To Answer Questions
Rob Spoor wrote:For n = 5, you don't add (5  1) and (5  2) (or 4 and 3), you add fibonacci(4) and fibonacci(3). This is the same as (fibonacci(3) + fibonnaci(2)) + (fibonnaci(2) + fibonacci(1)), etc.
Rob Spoor wrote:For n = 5, you don't add (5  1) and (5  2) (or 4 and 3), you add fibonacci(4) and fibonacci(3). This is the same as (fibonacci(3) + fibonnaci(2)) + (fibonnaci(2) + fibonacci(1)), etc.
Campbell Ritchie wrote:Kaldewaaij taught Rob.
SCJP 1.4  SCJP 6  SCWCD 5  OCEEJBD 6  OCEJPAD 6
How To Ask Questions How To Answer Questions
Campbell Ritchie wrote:I trust you know that particular algorithm is often used as an example of exponential complexity. There are algorithms which run in linear complexity or even logarithmic complexity, but that algorithm runs in approx. 1.608ⁿ complexity. If you try it wih larger arguments, e.g. 30‑40, you will find it becomes inordinately slow and maky even run out of memory. For the most efficient algorithm, find Anne Kaldewaaij's book, about page 98. Kaldewaaij taught Rob.
I was taughtt that there is no such thing as fib(0), and that the sequence starts with fib(1) (=1) and fib(2) (=1). There are other Fibonacci series starting with different numbers, but what you have calculated is what people understand by Fibonacci series not otherwise specified.
You should by no means regard recursion as a solution of last resort. Recursion is good, but that particular example has its problems.Joshua Soeng wrote:. . . Yes, I've read about the downside of recursion, and that we should treat recursion as a last resort . . .
That's a pleasure The log(n) solution is, I think, the third in Rob's list.Thank you for your information Campbell.
Joshua Soeng wrote:Yes, I've read about the downside of recursion, and that we should treat recursion as a last resort, but I'm just curious about recursion.
Campbell Ritchie wrote:The log(n) solution is, I think, the third in Rob's list.
SCJP 1.4  SCJP 6  SCWCD 5  OCEEJBD 6  OCEJPAD 6
How To Ask Questions How To Answer Questions
Joshua Soeng wrote:Yes, I've read about the downside of recursion, and that we should treat recursion as a last resort, but I'm just curious about recursion.
An IDE is no substitute for an Intelligent Developer.
Tim Holloway wrote:So don't avoid recursion just to be "efficient". Only be efficient when you detect that you're being inefficient. The recursive solution is often easier to read and understand, and these days, it's the humans that are the expensive part of the system.
Practice only makes habit, only perfect practice makes perfect.—every music teacher ever
Practice mindfully by doing the right things and doing things right.— Junilu
[How to Ask Questions] [How to Answer Questions]
Aaaaaaaaaaaaaaaaaaaaah! So that's what tail recursion is.Tim Holloway wrote:. . . . a pathological case called "tail recursion" and unless I miss my guess, this Fibonacci sequence is an example of such.
My gcc compiler didn't detect it. When I mistakenly calculated fib(20) 40×, you can see the optimisation:but we can see the times converging on the Golden Ratio, 1.61803….I think I have once counted the recursive calls and found that the count is a Fibonacci number. Try it. Change this function:toTail recursion is usually detected and optimized by modern compilers. . . . .
I have just done so and found that in Java® too, the ratio of successive durations converges on the Golden Ratio, but the counts weren't Fibonacci numbers.Earlier this morning, I wrote:I think I have once counted the recursive calls and found that the count is a Fibonacci number. Try it. . . .
An IDE is no substitute for an Intelligent Developer.
That's a pleasureJoshua Soeng wrote:. . . . Thanks a lot everyone . . . thank you.
An IDE is no substitute for an Intelligent Developer.
An IDE is no substitute for an Intelligent Developer.
Campbell Ritchie wrote:Not convinced about line 7. I was taught that the Fibonaccci series starts at Fib(1), so there is no such thing as Fib(0). That will give Fib(9) as 55, but 55 should be Fib(10). I think you need to change those numbers from 0, 1 to 1, 2.
Campbell Ritchie wrote:Not convinced about line 7. I was taught that the Fibonaccci series starts at Fib(1), so there is no such thing as Fib(0).
Hahahahahahahahahahahaha!Piet Souris wrote:. . . That was before the war, when there were no computers. . . .
no wonder he is so sad, he hasn't seen this tiny ad:
Programmatically Create PDF Using Free Spire.PDF with Java
https://coderanch.com/wiki/703735/ProgrammaticallyCreatePDFFreeSpire
