posted 11 years ago
I wrote this basic fibonacci recursive method, as a way of learning recursion. But compared to an older version of the same program this one runs much slower. Is this common with recursion? what could be causing this?
[ April 02, 2006: Message edited by: Stephen Foy ]
[ April 02, 2006: Message edited by: Stephen Foy ]
Stephen Foy  Microsoft Application Development Consultant
posted 11 years ago
Hi Stephen,
calculating the 100th Fibonacci number is very time consuming.(as you know I presume)
recursive method explained:
The process builds up a chain of deferred operations.
(in this case,a chain of additions>recursive process).
If you want to visualize this,take a paper and a pencil and substitute the appropriate values.
Carrying out this process requires that the interpreter keep track of the operations to be performed.The length of the chain (and the information needed to be kept ) grows linearly with n.
(Big O notation O(n) )
Hope this helps
[ April 02, 2006: Message edited by: Stephan Norwood ]
[ April 02, 2006: Message edited by: Stephan Norwood ]
calculating the 100th Fibonacci number is very time consuming.(as you know I presume)
recursive method explained:
The process builds up a chain of deferred operations.
(in this case,a chain of additions>recursive process).
If you want to visualize this,take a paper and a pencil and substitute the appropriate values.
Carrying out this process requires that the interpreter keep track of the operations to be performed.The length of the chain (and the information needed to be kept ) grows linearly with n.
(Big O notation O(n) )
Hope this helps
[ April 02, 2006: Message edited by: Stephan Norwood ]
[ April 02, 2006: Message edited by: Stephan Norwood ]
Stephen Foy
Ranch Hand
Posts: 143
posted 11 years ago
Just nitpicking here, but since each call to "calculate" triggers two more calls, this isn't linear complexity O(n), but exponential complexity  O(2^n). That's what makes Fibonacci numbers such a bad example of recursion: It can be calculated with linear complexity, but calculated recursively, it's exponential.
Calculating factorials is an example of a linear recursion.
[ April 02, 2006: Message edited by: Ulf Dittmer ]
Calculating factorials is an example of a linear recursion.
[ April 02, 2006: Message edited by: Ulf Dittmer ]
Curse your sudden but inevitable betrayal! And this tiny ad too!
ScroogeXHTML 7.1  RTF to HTML5 / XHTML converter
https://coderanch.com/t/690611/ScroogeXHTMLRTFHTMLXHTMLconverter
