如何在APL中实现互递归？——Dyalog APL Win10下递归无法终止问题解决

你碰到的问题根源在于Dyalog APL的布尔运算符∨和∧是严格求值的——它们会先把左右两边的表达式全部计算完，再执行逻辑运算，并不会像Python、JavaScript这类语言的or/and那样短路终止。这就导致你的递归会无限深入下去，最终耗尽工作空间（WS），抛出WS FULL错误。

正确的函数式互递归写法 #

我们可以用dfn的条件分支语法（: ⋄）来模拟短路逻辑，让递归在触发终止条件时立刻停止，完全符合你想要的函数式风格：

even ← { ⍵=0: 1 ⋄ odd ⍵-1 }
odd ← { ⍵≤0: 0 ⋄ even ⍵-1 }

代码逻辑拆解 #

• even函数：如果输入的⍵等于0，直接返回1（这是终止条件，0是偶数）；否则调用odd ⍵-1继续递归判断。
• odd函数：如果输入的⍵小于等于0，直接返回0（终止条件，非正整数不可能是奇数）；否则调用even ⍵-1继续递归判断。

现在测试一下，结果完全符合预期：

even 7  ⍝ 返回0（7是奇数）
odd 7   ⍝ 返回1（7是奇数）
even 0  ⍝ 返回1（0是偶数）
odd 0   ⍝ 返回0（0不是奇数）

原代码失败的原因 #

举个具体的例子，当执行even 0时，原代码(odd ¯1) ∨ 1会先计算odd ¯1，而odd ¯1的表达式是(even ¯2) ∧ 0，又会先计算even ¯2……这个过程会无限递归下去，因为没有机会触发终止条件直接返回，最终把工作空间的内存耗尽，才会出现WS FULL错误。

内容的提问来源于stack exchange，提问作者Miroslav Popov