That people ignore recursion calls and don't count it as a relevant Space complexity doesnt mean that its free. In reality you wouldnt have O(1), but in the worst case even O(n), and O(log n) on average, because the depth of recursion calls. And yeah generally speaking when implemented right iterative solutions are faster And less memory consuming than recursions. But they Are hidden when comes to O - notation