Church Turing thesis highlights the equivalence between different computability models.
Using recursion we don’t need a mutable state while solving some problem, and this make possible to specify a semantic in simpler terms. Thus solutions can be simpler, in a formal sense.
I think that Prolog shows better than functional languages the effectiveness of recursion (it doesn’t have iteration), and the practical limits we encounter when using it.