Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

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

 
john sayeau
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • 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:



 
Campbell Ritchie
Marshal
Posts: 55680
161
  • Mark post as helpful
  • send pies
  • 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.
 
Andrey Kozhanov
Ranch Hand
Posts: 79
  • Mark post as helpful
  • send pies
  • 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: 55680
161
  • Mark post as helpful
  • send pies
  • 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.
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16026
87
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • 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
  • Quote
  • Report post to moderator
Thanks guys.
 
Campbell Ritchie
Marshal
Posts: 55680
161
  • Mark post as helpful
  • send pies
  • 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
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!