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