• 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

using this recursive method slows me down....why?

 
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I was just fooling around comparing ruby and java performance and noticed that if I use the java code below with a recursive method that produces fibonacci numbers it runs way slower that the second section of code. Same thing happens with ruby...so what am i doing wrong?


here is the slow code with output:

output:



faster code:


here is the output:



 
Marshal
Posts: 79180
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Are you using the Fibonacci generator which include fib(i - 1) + fib(i - 2) or similar? That method is notorious for running in exponential time, and is givien to beginners as an example of how not to write recursion. If you search, you will find more details; there is something about it in this old thread.
 
Ranch Hand
Posts: 79
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Nothing strange here. Recursive algorithms always runs slower than ones that don't use recursion. That's because additional time is needed to pass parameters into function.
 
Campbell Ritchie
Marshal
Posts: 79180
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This is your code, which I have made some additions and alterations to:Check that for spelling and compiler errors, and you will see how many calls there are to the recursive methods.
 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Andrey Kozhanov wrote:Nothing strange here. Recursive algorithms always runs slower than ones that don't use recursion. That's because additional time is needed to pass parameters into function.


But in this case that is not the reason why it runs so slow. Check out Campbell's version.

The recursive version does far too much work. Suppose that you put in the number 10. In line 21 (in John's original version) it's going to call fiboGen(9) {a} and fiboGen(8) {b}.

{a} The call fiboGen(9) is going to do fiboGen(8) {c} and fiboGen(7) {d} in line 21.
{b} The call fiboGen(8) is going to do fiboGen(7) {e} and fiboGen(6) {f} in line 21.

{c} The call to fiboGen(8) is going to do fiboGen(7) {g} and fiboGen(6) {h} in line 21.
{d} The call to fiboGen(7) is going to do fiboGen(6) {i} and fiboGen(5) {j} in line 21.
{e} The call to fiboGen(7) is going to do fiboGen(6) {k} and fiboGen(5) {l} in line 21.
{f} The call to fiboGen(6) is going to do fiboGen(5) {m} and fiboGen(4) {n} in line 21.

You can start to see what is happening here: fiboGen(7) is already calculated three times {d}, {e} and {g}, fiboGen(6) is calculated four times {f}, {h}, {i}, {k}, etc.

So it is doing the same calculations many times, instead of just calculating each input only once.

Cambell's counter shows that for fiboGen(40) the method is called 331,160,281 times. The version with the loop just has to iterate over the numbers once (so just 40 iterations in total).
 
john sayeau
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks guys.
 
Campbell Ritchie
Marshal
Posts: 79180
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
. . . but for fiboGen(39) it is 204668309 calls. The interesting thing is that 331160281 ÷ 331160281 = 1.6180339917695807024. And if we look up the Golden Ratio (φ) it comes to 1.6180339887498948482
 
reply
    Bookmark Topic Watch Topic
  • New Topic