Every properly programmed recursive function beats the living shit out of non-recursive functions. Here's an example. I've programmed two different programs which count the n:th fibonacci number (f0 = 0, f1=1). The first one is a recursive mother fucker optimized with dynamic programming. This little bugger runs more than twice as fast as the non-recursive version below!
So this one runs in like 0.03 seconds on my machine for n = 30k which is pretty good.#python2 fib_dyn.py 0.02s user 0.01s system 94% cpu 0.028 total
#python2 fib_dyn.py 0.02s user 0.01s system 88% cpu 0.034 total
import sys
sys.setrecursionlimit(100000)
x = 30000
fibs = [-1] * (x+1)
def fib(n):
if fibs[n] != -1:
return fibs[n]
if n == 0:
return 0
if n == 1:
return 1
fibs[n] = fib(n-1) + fib(n-2)
return fibs[n]
ans = fib(x)
And this piece of shit runs in about 0.07s, which is more than twice as much as the previous.#python2 fib_lin.py 0.06s user 0.01s system 93% cpu 0.072 total
#python2 fib_lin.py 0.06s user 0.00s system 96% cpu 0.069 total
x = 30000
a = 0
b = 1
i = 0
while i < x - 2:
y = b
b += a
a = y
i += 1
ans = a+b
What is stack depth and readability?
All recursive functions have the potential to exhaust the stack. Iteration never has this problem. Recursion is just for try-hards.
>>51795195
nice bait
You use the function that best fits the job you need done.
>>51795231
Run the programs yourself and explain to me why the first one is twice faster than the second then.
>>51795273
Because you chose to sacrifice readability and stack safety in favor of literally 3 hundreths of a second speed increase.
>so smert
Use the right tool for the job it's that simple
>>51795229
A recursive procedure can run as an iterative process. Do you know what a tail recursive function is?
>>51795273
Speed is not the issue. The entire problem is the stack, which can get filled up very quickly. If you really needed to write a program which did some calculation requiring you to ask for some value of fib(n) repeatedly, the smart thing to do would be to pre-compute most of the values and throw them into an array. If all you're trying to do is generate the fibonacci numbers, the iterative function would be able to calculate far more terms than the recursive one because of the stack.
>>51795219
>>51795229
>>51795362
>>51795381
>implying recursion requires all calls to be put on the stack
>implying all good languages don't have tail recursion
also how the fuck is a non-recursive solution any more readable? the only difference is that one requires you to understand the idea of recursion (and not much else) while the other requires you to be able to easily follow the changes of mutable state for certain variables. you can look at a recursive functions and immediately see the intent but if you look at the iterative one you're pretty much forced to think through the whole thing.
>>51795596
This. Recursive functions have the advantage of being much more readable.
>>51795362
>sacrifice readability
You do know the Fibonacci function is defined recursively, right? This is a textbook (memoized) implementation, albeit in the worst possible language for this.
