Or say, do multicore CPUs process recursion faster than iteration?
Or it simply depends on how one language runs on the machine? like c executes function calls with large cost, comparing to doing simple iterations.
I had this question because one day I told one of my friend that recursion isn't any amazing magic that can speed up programs, and he told me that with multicore CPUs recursion can be faster than iteration.
If we consider the most recursion-loved situation (data structure, function call), is it even possible for recursion to be faster?
So how are the multicore cpus performing for now? Are the softwares nowadays all programed for multi-core cpus?
There are really two ways to look at this problem:
1. Looking purely at the compiled code, then yes, iteration is faster than recursion. This is because recursion adds a function call (=overhead), and iteration does not. However, a common type of recursion is tail recursion: the recursive call is made at the end of the function. This is always optimized to iteration by compilers. So in that case it does not matter. Ergo: in some cases recursion is slower, but it is never faster.
2. From a functional programming viewpoint, most of the time recursive functions are written to be without side effects. (Having side effects in a recursive function would make it really difficult to get it to produce correct results.) If a function doesn't have side effects, then it is trivial to parallelize (thus easier to run on a multicore system). This isn't a property of recursive functions per se, but that could be the reason why your friend argues that recursion can be faster than iteration.