Turing complete; this means that they are as powerful (they can be used to solve the same problems) as imperative languages based on control structures such as and .

Repeatedly calling a function from within itself may cause the call stack to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less efficient,