I read cost of recurcion more than a loop. Is this the reason?
I think some programs in OCaml can be and are faster than equivalent in C.
2 Likes
There are some functional things in Rust, AFAIK.
But, I think it’s more about abstraction costs in general, you see imperative programming is way more explicit to machine to understand and execute, it relies heavily on developer’s skills to implement things the way he intended it to be, but you could say that programmer could do that in similar manner but then it’s not functional, it loses all the features functional style gives to developer to operate with, functors, monads (well, you could argue with this one), applicatives, immutability, multithreading model and other cool stuff which are quite expensive both at runtime and compile time.
So the question is more like - why do people don’t develop at system level in functional style? Because it’s costly
2 Likes
There is no cost in recursion that extends the cost of a loop. Both are (un)conditional jumps when it comes to Assembler.
The main reason why equivalent programs are often not as fast as C is mainly caused by additional runtime environments, garbage collectors and such stuff. Also immutability does cause a lot of copying values around that you would manipulate inplace in C/C++.
Also the array vs. lists misunderstanding causes some speed issues, but those are related to the programmer, not the language. Random access in a list is bad in C as well 
9 Likes
thanks for replies @sztosz @dixi-sixi @NobbZ
Ofcourse everything depends on programmer.
Some programs can be faster in a spesific language. I just mean general situations.
I read calling a function harder. And that is why article owner wrote recursion is slower than a loop. But as you say a loop already function right ? So there is no reason slowness from recursion.
At the end of the day, we can be as functional as we want, the code is compiled and runs on a Turing machine… There are some dedicated FP chipset, and it would be nice to build a functional computer 
3 Likes
Yes, calling a function is in fact costly due to housekeeping the stack, but if you do recursion right the function calls can get optimized away. This is called tail-call-optimization.
Which article owner? Can you share a link?
No, I did not. I said that loops and recursion boil down to jumps, and I assumed properly written and optimized tail call recursion. Calling a function is much more than a simple kump. It does also involve writing its arguments values to the stack, the return address to the stack and perhaps other bookeeping I do not remember right now. On returning those pushes to the stack have to be rolled back. That makes function calls costly and inlining functions can reduce this costs.
3 Likes
It is a recursion C article non-english.
Really informative but I need to search some things to understand. Thanks again 
1 Like
If you want something FAST go RUST …
It has some functional aspects.
Rust crate live-coding (part 1) Running jobs on AWS EC2 (scheduler in rust)
4 Likes
Rust is great language, in my list. I created this topic just for information. Even ruby is fast for my algorithms. I am not benchmark guy 
1 Like
Which language is it then? Perhaps we have some people in the forum that do speak and understand that language and are able to comment properly. So I’d be really happy if you’d share the link.
Also modern C compilers (at least CLang and GCC) do proper TCO if not deactivated. So if you have really a slowdown between equivalent loop and TC-recursion, then those are with a high chance not equivalent or you did wrong settings on your compiler.
Go, Python, and Java (and others on the JVM) are the only 3 languages I am aware of right from my fore head, that do not do TCO and therefore force you to carefully write your loops. Both have different reasons for that. For python there are final words on TCO available, for go I’ve once heard that detecting TCs would hurt compilation speed to much. JVM-stuff did never explain to me why, well, clojure people once told me, clojure does not do it automatically bacause Java doesn’t do as well…
5 Likes
For more explaination just basic article how to recurcion in C. Article owner wrote if you have, too many function calls in recurcive funtion, loop will be faster. Because calling a function cost more than loop. I havent compared C codes , I am not C coder. Currently i am only trying improve my elixir skills. But hard to find algorithm articles for elixir. Elixir is nearly my first programing language i just have some basic rails background
Well, if your “many” function calls are “inner” calls, which return to the place they were called from and are the very same after rewriting into a loop, then you have gained nothing.
If your function calls can be replaced by a loop and bookkeeping variables, then the compiler would have been able to do so as well with a very high chance.
I’m still asking for the link to the article…
1 Like
i couldnt find past article but that english article tells samething
I think Haskell and OCaml are pretty much up there on the faster languages pool. Given the same amount of time to work on a same problem with C++, Haskell, and OCaml, the performance would be roughly the same, since they all compile down to native code (no VM, runtime, etc.). Of course, given more time, the C++ code would be able to be optimized through low-level constructs, while Haskell and OCaml would suffer from garbage collection (whether it’s significant I don’t really know).
Also, I think the procedural nature of computers also gives the benefit of easier mapping from C and C++ instructions to machine code, while Haskell and OCaml’s compiler need to do the extra work of mapping the two different world of representation.
Having said that, I can argue that OCaml’s compilation time is blazingly fast, while I have heard (and in case of Haskell, experienced) scary stories about C++ and Haskell compilation times.
I also don’t think recursion have anything to do with it; tail calls are reduced to loops so there’s no overhead there.
(This was all from my understanding and I may very well be mistaken at some points.)
3 Likes
Yupp, and none of them is written in a way that may benefit from TCO. I do not understand their benchmarking table though… And as such I can’t measure or compare the following code to theirs.
Also as I’ve not done C/C++ for a while the following snippets are untested and only in C-like pseudosyntax.
int fact(int i) {
return do_fact(i, 1)
}
int do_fact(int i, int res) {
if i <= 1
return res;
return do_fact(i-1, res * i);
}
int fib(int n) {
return do_fib(n, 0, 1)
}
int do_fib(cur int, n int, old int, new int)
if(n == 0)
return old;
return do_fib(cur - 1, new, old + new);
}
I might misremember the fib implementation, but I should be close enough to off by only one
9 Likes
A lie! I can’t see any parenthesis!
7 Likes
What do you mean functional computer ?
1 Like
Computer where chipsets are designed for FP operations…
Some example of chipsets done for FP.
3 Likes
