Recursive Fibonacci slow?

Question

In the latest 'question' of Marcel, he shows that a Fibonacci, using a recursive function times out, where using a loop is very quick.
does anybody know WHY this is the case?
does calling a method comes with an overhead, or is the compiler just able to optimize a loop better than a recursive function?
https://www.sololearn.com/discuss/919091/?ref=app

Answer 1

Well for loops are more efficient than multiple returns
In a for loop:
#
#
#
...
#
in a recursive function:
#,break
#,break
#,break,
...
#,break
Where # are the functions being executed.

Answer 2

I've spent some time on timing Python Fibonacci calculations just to see the order of difference. See the code first. You can play with floating point formula, iteration , recursion(optimized) and see timing. https://code.sololearn.com/cQ82uZAUYiwu/?ref=app

Answer 3

If you can make you code without recursion-you should do it. It will take time to call the function and it will take memory (in the stack) to provide all functions parameters. If recursion calling will be very deep it even can overload memory and crash the program.

Answer 4

hmmm, that's sounds very logical...
thanks for this clear explanation.