Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
JavaRanch.com/granny.jsp
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Devaka Cooray
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Junilu Lacar
  • Paul Clapham
  • Knute Snortum
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • salvin francis
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Ganesh Patekar

Fibonacci in C++  RSS feed

 
Greenhorn
Posts: 19
Java jQuery Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, I have a question about this Fibonacci Program using Recursion.
I've been comparing several codes for Fibonacci and I'm sure this code snippet is correct, however I'm missing the logic here.

So this is the code snippet:


If I go step by step:

n = 0;
return 0;

n = 1;
return 1;

n = 2;
return(fibonacci(2-1) + fibonacci(2-2)) --> return(fibonacci(1) + fibonacci(0)) = 1;

n = 3;
(3-1) + (3-2) = 3;

n = 4;
(4-1) + (4-2) = 5;

n = 5;
(5-1) + (5-2) = 7;

n = 6;
(6-1) + (6-2) = 9;

n = 7;
(7-1) + (7-2) = 11;

Result should be 0, 1, 1, 2, 3, 5, 8, ...
But why is it all messed up?
Could anyone please explain it to me where did I miss the logic?

Thank you.
 
Sheriff
Posts: 21602
101
Chrome Eclipse IDE Java Spring Ubuntu VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Joshua Soeng
Greenhorn
Posts: 19
Java jQuery Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.



Ah, so the logic is supposed to be like this?

 
Joshua Soeng
Greenhorn
Posts: 19
Java jQuery Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.



Thank you so much Rob.
 
Marshal
Posts: 62819
203
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Rob Spoor
Sheriff
Posts: 21602
101
Chrome Eclipse IDE Java Spring Ubuntu VI Editor Windows
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Kaldewaaij taught Rob.


Not directly, I was only taught using his book.

But Campbell is right about this recursive variant having terrible performance. I actually know of four implementations:
* This recursive variant.
* One that uses a loop and keeps track of the current and previous values (chapter 4.3 of Kaldewaij's "The Derivation of Programs").
* One that uses a matrix (chapter 5.2 of Kaldewaij's "The Derivation of Programs").
* One that uses a direct function applied to the input to get an approximation (listed at https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression).

[edit]Kaldewaij, not Kaldewaaij, and it's a man[/edit]
 
Joshua Soeng
Greenhorn
Posts: 19
Java jQuery Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.



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.
Thank you for your information Campbell.
 
Campbell Ritchie
Marshal
Posts: 62819
203
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Joshua Soeng wrote:. . . Yes, I've read about the downside of recursion, and that we should treat recursion as a last resort . . .

You should by no means regard recursion as a solution of last resort. Recursion is good, but that particular example has its problems.
Other problems: A deep or infinite recursion may run out of memory or stack space, which is different from an infinite loop. There are things which cannot be calculated with a loop, only recursion.

Thank you for your information Campbell.

That's a pleasure The log(n) solution is, I think, the third in Rob's list.
 
Rob Spoor
Sheriff
Posts: 21602
101
Chrome Eclipse IDE Java Spring Ubuntu VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.


As Campbell said, there is nothing wrong with recursion itself. The problem arises when applied incorrectly or unnecessarily. I had a problem with Hibernate with a query that used an IN statement with over 200 elements in the collection. The implementation used recursion to go over a list (using a "delegate to next" approach where "next" involved a method call) that caused StackOverflowErrors. If that would have been a list (and so simple it would have been...) there would be no issue.

Campbell Ritchie wrote:The log(n) solution is, I think, the third in Rob's list.


It is. These four implementations have, respectively:
* terrible complexity
* linear complexity
* logarithmic complexity
* constant complexity (assuming your CPU supports it)
 
Bartender
Posts: 20310
110
Android Eclipse IDE Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.



Actually, there's a pathological case called "tail recursion" and unless I miss my guess, this Fibonacci sequence is an example of such. Tail recursion is usually detected and optimized by modern compilers. They replace the repeated calls with a loop in the generated code, eliminating the costs of setting up and disposing of stack frames, pushing/popping parameters and results and so forth.

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.
 
Sheriff
Posts: 12963
217
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.


A thumb is not enough to voice my support of this thought so have a cow instead.
 
Campbell Ritchie
Marshal
Posts: 62819
203
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:. . . . a pathological case called "tail recursion" and unless I miss my guess, this Fibonacci sequence is an example of such.

Aaaaaaaaaaaaaaaaaaaaah! So that's what tail recursion is.

Tail recursion is usually detected and optimized by modern compilers. . . . .

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:-to
 
Campbell Ritchie
Marshal
Posts: 62819
203
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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

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.
 
Campbell Ritchie
Marshal
Posts: 62819
203
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have remembered how to get the count as a Fibonacci number:-Initialise count to 1 and only increment it when there is a recursive call:-I tried some bigger numbers and fib(47) would overflow an int.
 
Tim Holloway
Bartender
Posts: 20310
110
Android Eclipse IDE Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Since we're looking at gcc, here's some links about how it optimizes tail recursion. And one of them is about the Fibonacci sequence!

http://32leav.es/?p=674 How gcc optimizes tail recursion.

https://stackoverflow.com/questions/490324/how-do-i-check-if-gcc-is-performing-tail-recursion-optimization
 
Joshua Soeng
Greenhorn
Posts: 19
Java jQuery Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sorry for my slow reply. Thanks a lot everyone for your help and references, you've been very helpful, thank you.
 
Campbell Ritchie
Marshal
Posts: 62819
203
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Joshua Soeng wrote:. . . . Thanks a lot everyone . . . thank you.

That's a pleasure
 
Campbell Ritchie
Marshal
Posts: 62819
203
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I tried a couple of optimisations; it took me a long time to understand the links Tim gave, and I thought the flag was -02 when it should be -O2, but I still seem to be in 1.618 time. My C function appears to be proper tail recursion:-
 
Tim Holloway
Bartender
Posts: 20310
110
Android Eclipse IDE Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Have you tried it with if/then logic? It may be that the trinary construct is confusing the optimiser.

Also it would be interesting to see what you measure if you use a switch/case!

Two other observations: 1: you don't return the proper value for fib(0). 2: your handling of fib(2) might also confuse the optimiser.
 
Campbell Ritchie
Marshal
Posts: 62819
203
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I was taught there is no such thing as fib(0). I shall try an if‑else.
 
Campbell Ritchie
Marshal
Posts: 62819
203
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Maybe I should give up.The reason the small numbers give strange timings is that the clock() function counts as if in μs and I started it from 1μs so as not to start with a divide by zero error. No difference with the -O2 option.
 
Tim Holloway
Bartender
Posts: 20310
110
Android Eclipse IDE Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I had similar frustrations when I did an implementation of the Black-Scholes process where I was building successive layers of a tree. In my case, a third party suggested that I cache my intermediate results. I hadn't done that because the individual operations were so trivial that I didn't think it would matter, but I tried and the result was the fastest implementation the suggester had ever seen.

Without looking at the generated assembly code to be sure, what I'd suspect is that the optimiser isn't considering the fact that you could use the pre-computed fibonacci_inefficient(i - 2) to do most of the work of computing fibonacci_inefficient(i - 1) and thus doubling up on the work required.

Since you're not that far off the touted tail recursion example I can really only think of 2 reasons for disappointment: 1) you might be falling slightly short of the optimiser's Fibonacci detector or 2) they considered their optimisation to be so significant that they didn't consider any less pure code options.

I did go back and check and the example does say that with -O2 there's still recursion going on, just that it eliminated recursion on one side. Which means that at least you're running a straight line and not a tree.
 
Campbell Ritchie
Marshal
Posts: 62819
203
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you. I know I could write a Fibonacci implementation using the two previous numbers; in fact I suspect the remainder of that file contains exactly that. And this will run nicely in linear time. I have tried successfully implementing Kaldewaij's algorithm, but I have forgotten all its details.
 
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


Any Fibonacci Sequence within Seconds using Hashmap and BigInteger.

 
Campbell Ritchie
Marshal
Posts: 62819
203
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Mark Ii
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.



Thank you Sir.
 
Master Rancher
Posts: 3080
108
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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 was before the war, when there were no computers.      
 
Campbell Ritchie
Marshal
Posts: 62819
203
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:. . . That was before the war, when there were no computers. . . .

Hahahahahahahahahahahaha!
 
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/Programmatically-Create-PDF-Free-Spire
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!