3 ms·
You can design languages that have only iteration, such as Dijkstra's guarded command language extended with data types, or have only recursion, such as the lam
by chalst 15y ago
You can design languages that have only iteration, such as Dijkstra's guarded command language extended with data types, or have only recursion, such as the lambda calculus, and each can code up the other as an interpreter. So there is a basic sense in which neither is more expressive than the other.
But there is a sense in which recursion is more expressive than iteration, in the sense of being a flexible local abstraction: in a language with tail recursion, iterative loops can be directly encoded by means of recursive calls. And indeed this is how iteration is expressed in the Scheme language. Trying to encode recursion in terms of iteration cannot be done so directly.