[a / b / c / d / e / f / g / gif / h / hr / k / m / o / p / r / s / t / u / v / vg / vr / w / wg] [i / ic] [r9k / s4s / vip / qa] [cm / hm / lgbt / y] [3 / aco / adv / an / asp / bant / biz / cgl / ck / co / diy / fa / fit / gd / hc / his / int / jp / lit / mlp / mu / n / news / out / po / pol / qst / sci / soc / sp / tg / toy / trv / tv / vp / wsg / wsr / x] [Settings] [Search] [Mobile] [Home]
Board
Settings Mobile Home
/g/ - Technology


Thread archived.
You cannot reply anymore.



File: fibonacci.png (45 KB, 1170x597)
45 KB
45 KB PNG
>tfw c has no tail-recursion optimizing algorithm

regardless, how exactly are tail-recursive algorithms expanded? Spent a solid 20m transforming recursive fibonacci into iterative (partly because i'm a brainlet)
>>
faggot just do -O2
>>
>>76585574
tried, even with -O3

[sandbox] 0; time ./main --recursive
fib(40): 165580141

real 0m0.449s
user 0m0.443s
sys 0m0.004s
[sandbox] 0; time ./main
fib(40): 165580141

real 0m0.003s
user 0m0.002s
sys 0m0.001s
[sandbox] 0;
>>
Recursives are always slower than iterative I thought
>>
>>76585653
yes they are, but it's easier to wrap your head around certain recursive algorithms
>>
>>76585474
Anon, you realize that the naive recursive implementation of the fibonacci function is not tail recursive, right?
>>
What do you mean by "expanded"?

I thought tail-call recursion was a stack-space optimization, not a performance optimization.
>>
>>76585626
i googled it and apparently it does have tail recursion, my guess is that fibonacci can't be optimized that way ¯\_(ツ)_/¯
>>
>>76585474
>>tfw c has no tail-recursion optimizing algorithm
There is, it's how Chicken Scheme works.
>>
>>76585474
Clearly someone hasn't been reading their SICP.
Fibonacci can be done with tail-recursion, and gcc creates the same assembly for the two versions.
https://godbolt.org/z/4blcXC
>>
>>76585684
>fibonacci can't be optimized that way
I'm just gonna assume you were too dumb to do it correctly. Feel free to post your code and prove me wrong.
>>
>>76585474
the stack frame for the current function isn't needed at the end so you replace the entry with the stack frame from the function you call.
>>
>>76585679
Depends on how it is implemented. Most better compilers will attempt to rewrite the tr func as a loop which can improve performance somewhat. Lesser compilers will pop the frame then call the function normally, ensuring no stack growth but otherwise not really helping performance over a non-tr version.
>>
>>76585474
>1.3 seconds
are you writing it like
 int fib(int n) { return fib(n-1) + fib(n-2) ;}

of couse tail call optimization doesnt work for that.
>>
>>76585474
>claims there isn't tail end recursion without ever looking at the disassembly
retard
>>
>>76585474
here i'll do it iteratively for you
>int fib(int n){
>double f;
>while(f = sqrt(5))
> return pow(f/2,n)/f + .5;
>}
>>
>>76585474
the optimization for tail recursion is to optimize out the recursion you brainlet, the compiler did it's job
>>
>>76585474
>why won't my exponential time algorithm work as fast as my linear time algorithm
>>
>>76585474
>fibonacci
is not a tail-recursion
>>
>>76585474
>recursion
Fucking python faggots
>>
>>76585653
They are but they're often easier to write, read, and maintain
Can you imagine writing an iterative top-down parser? That sounds like hell
>>
File: 1244654564678.jpg (54 KB, 349x427)
54 KB
54 KB JPG
>>76585985
fibonacci isnt tail recursive retard
>>
Code that's not retarded (unlike OP's code and OP):
static int fibrec_helper(int a, int b, int n) {
if (n != 0) return fibrec_helper(b, a + b, n - 1);
return a;
}
int fibrec(int n) {
return fibrec_helper(1, 1, n);
}

int fibiter(int n) {
int a = 1, b = 1;
while (n != 0) {
int sum = a + b;
a = b;
b = sum;
n -= 1;
}
return a;
}

Read the assembly and weep: https://godbolt.org/z/rgPZcF
>>
File: fib.png (62 KB, 560x647)
62 KB
62 KB PNG
>>76589208
Well, well, well... The actually good solution is better than OP's shit solution, who would have guessed.
OP is that dude that says "Oh, C++ is easy, I don't see the big deal with it"
>>
>>76589208
Is there an advantage of the while loop? It seems to me that a for loop would be more suitable.
>>
>>76589208
Also n != 0 would give weird results for negative n, or is it more efficient than n>=0?
>>
>>76585474
Retard, gcc is open source so implement it ypurself
>>
>>76588404
>fibonacci isnt tail recursive retard
Any iteration can be translated into tail-recursive function calls, retard.
But the really retarded thing is writing a non-tail-recursive algorithm and expecting the compiler to somehow, magically make it go away.
>>
>>76589208
Why not write it
static int fibrec_helper(int a, int b, int n) {
if (n == 0) return a;
return fibrec_helper(b, a + b, n - 1);
}
>>
>>76585653
If it's an optimized tail call then its just as fast
>>
>>76589946
Who cares
The while loop is more readable than an equivalent for loop here



Delete Post: [File Only] Style:
[Disable Mobile View / Use Desktop Site]

[Enable Mobile View / Use Mobile Site]

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.