摘要：某些语言禁止递归以确保程序终止。这在技术上是正确的，但通常是无关紧要的。
在我的职业生涯中，有三次我致力于一种经历了演变的编程语言：
禁止递归和无界循环。声明该语言是图灵不完整的，所有程序都将终止。
声明图灵不完整的程序更简单。让非技术人员将快速终止与最终终止混为一谈。
意识到缺乏递归使得表达事物变得极其笨拙，把简单的问题变成了脑筋急转弯。
在我离开大学之前，这个过程听起来很可笑。事实上，即使在这些步骤发生了两次之后，我仍然相信这种事情永远不会再发生。现在我有了三个例子，似乎值得写一篇博客文章，所以对于第四个案例，我有一些东西可以参考。
首先，让我们考虑一种小型的、简单的、面向语句的一阶编程语言。我们怎样才能写出一个非终结性的程序呢？有两种简单的方法。首先，编写一个loop-While(True){}。第二，编写递归，void f(){f()}。我们可以禁止这两种情况，只留下x在xs{..中的表单的有界迭代。)或类似情况。现在图灵语言不完整，所有程序都会终止。
缺少递归使程序更难编写，但我们总是可以使用带有无界循环的显式堆栈。
如果我们对程序可能执行的步骤有一个上限，那么缺少无限循环并不是问题。例如，我们知道快速排序的最坏情况下的复杂度为O(n^2)，所以如果我们可以在(0，n^2){..。那么我们的程序中就会有足够多的步骤，以至于我们永远不会达到极限。
但是，如果我们的编程语言甚至没有提供范围函数呢？我们可以通过意识到在线性代码中可以产生指数级的大值来综合它。例如：
Double Xs=Xs++Xs--有条纹的x=Double(Double[x])。
函数Repeat 1对Double进行了10次调用，并创建了一个长度为2^10(1024)的列表。只要再有263个请求加倍，我们就会有一个足够长的清单，足以容纳宇宙中的每个原子。通过一些调整，我们可以使倍增在给定的界限上停止，并按顺序生成数字，给我们范围到我们选择的任何界限。
我们现在有一个包含三种技术的菜单，可以让我们编写几乎任何我们想要编写的程序：
首先，我们还没有一种完整的图灵语言。代码将终止。但不能保证需要多长时间才能终止。从技术上讲，需要一百万年才能完成的程序会终止，但很可能无法在真正的计算机上运行。对于我见过的图灵不完备性提升的大多数领域来说，运行几秒钟将是理想的。图灵的不完整完全无济于事。
其次，在一堆错综复杂的逻辑谜题中对程序进行编码后，代码就更难读懂了。虽然有三种通用技术可以对逻辑进行编码，但通常还有其他一些考虑因素会导致每个实例的解决方案各不相同。我已经用这种受限的语言编写了树遍历、排序和解析器-结果总是有很多注释和至少一个级别的不必要的间接。
最后，以如此复杂的风格编写的代码的性能通常要差得多。考虑快速排序--标准实现最坏情况下需要O(n^2)时间，而平均情况下需要O(Nlogn)时间，堆栈需要O(Logn)空间。如果在开始编码While循环之前采用构建O(n^2)列表的方法，那么最终将得到O(n^2)个空间和时间。此外，在普通的快速排序中，时间复杂度是计算廉价比较的次数，而在编码版本中，时间复杂度与分配有关，而作为一个常量因素，分配的成本可能要高得多。
大多数具有if/for等标准补语的语言(图灵不完整)不会从这一限制中获得任何好处。一个例外是在证明属性或进行分析的领域，举两个例子：
依赖类型的语言，比如Idris，它们通常有比仅仅禁止递归和无限循环复杂得多的终止检查器。
资源受限的语言，如休谟，它通过限制语言的表现力来实现更好的分析和实现技术。
这样的语言在工业中往往是罕见的。在我经历过的所有图灵不完全编程语言中，后来添加了递归，简化了程序，用这种语言编程变得更容易。
虽然我研究过的大多数语言都是在私下进行的，但有一种语言--来自Digital Asset的DAML--是在公开场合进行的。2016年，他们写道：
DAML被故意设计为不是图灵完全的。尽管图灵完全语言可以对任何业务领域进行建模，但它们在灵活性方面所获得的好处却失去了可分析性。
如果没有显式迭代器，可以使用递归。例如，让我们尝试编写一个反转列表的函数。
请注意，虽然我曾经在Digital Asset工作，但这些帖子既早于我在数字资产公司工作的时间，也早于我在那里工作的时间。