迭代与递归在计算能力上完全等价

用只有赋值语句和 while 循环的极简语言可以证明：把 while 结构替换成”每个程序单元允许递归调用自己”的结构后，两种语言能够互相模拟——凡是能用迭代表达的算法，都能对应地改写成递归，反之亦然。这个等价性最终依赖丘奇-图灵论题：这类极简语言的计算能力已经等价于图灵机，不存在能力更强的语言，因此增删某一种控制结构不会扩大或缩小语言能表达的问题范围。发散：这解释了为什么纯函数式语言可以完全不提供 while/for 却依然图灵完备——递归本身已经足以表达任何可迭代计算，”用哪种结构写代码”因此是表达力和可读性上的风格选择，而不是计算能力上的取舍。