recursion - 在 J 中创建递归默认函数

Question

我是 J 的新手，我一直在尝试创建一个斐波那契函数作为练习（始终是我在学习语言时创建的第二个函数）。我只是无法弄清楚我这样做的方式到底出了什么问题。我试图将其定义为默认，但如果参数大于 1，它就会挂起。

fib =: [ ` (($: (]-1)) + ($: (]-2))) @. (>&1)

我也尝试过明确地创建它，并且效果很好。

fib =: 3 : 'if. y>1 do. (fib (y-1)) + (fib (y-2)) else. y end.'

我试图通过将 3 替换为 13 来创建一种默契，但它引发了错误。

   fib =: 13 : 'if. y>1 do. (fib (y-1)) + (fib (y-2)) else. y end.'
|spelling error
|   if. y>1 do. (fib (y-1)) + (fib (y-2)) else. y end.
|   ^
|   fib=:    13 :'if. y>1 do. (fib (y-1)) + (fib (y-2)) else. y end.'

所以，我要求有人解释我在这里做错了什么。

Answer 1

好的，我找到了。我只通过默认生成器运行了递归块并得到了这个块。

   13 : '(f y-1) + (f y-2)'
([: f 1 -~ ]) + [: f 2 -~ ]

然后我将它插入到原始片段中，得到了这个。

fib =: [ ` (([: $: 1 -~ ]) + [: $: 2 -~ ]) @. (>&1)

这就像一个魅力。我还插入" 0到最后以使其接受列表。

Answer 2

这是我认为更清晰、更简洁的替代方案：

fibn =: (-&2 +&$: -&1)^:(1&<) M."0

与更规范的（伪代码）定义进行比较：

fib(n) = fib(n-1) + fib(n-2) if n > 2 else n

首先，与其使用带有动名词的[ `with @. (>&1)，不如使用^:(1&<). 对于f(n) if cond(n) else n，使用^:连词更惯用；^:0意思是“什么都不做”，^:1意思是“做一次”，所以意图很明确。@.更适合非平凡的行为。

其次，使用&bond/compose连接显着简化了train。重复使用[:and]是相当混乱和不透明的。使用将相关操作放在一起进行重构&：首先，拆分n为两个，即n-2and n-1，其次，fibn将这两个数字相加。

最后，"0用于列表处理和M.记忆。M.从性能的角度来看，这是相当重要的，因为规范定义的直接实现会fib(2)过度调用。使用内置的记忆副词，您可以吃蛋糕（一个简单的定义）并吃掉它（良好的表现）。

此特定定义的来源：f0b在此页面上。