Создание рекурсивной неявной функции в J

Question

Я новичок в J, и я пытался создать функцию Фибоначчи как упражнение (всегда вторая функция, которую я создаю при изучении языка). Я просто не могу понять, что именно не так на моем пути. Я пытался определить его как молчаливый, но он зависает, если аргумент больше единицы.

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

Вот альтернатива, которая, на мой взгляд, более ясна и кратка:

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

Сравните с более каноническим (псевдокодовым) определением:

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

Во-первых, вместо использования [ ` с @. (>&1), который использует герунд, лучше использовать ^:(1&<), За f(n) if cond(n) else n, с использованием ^: соединение более идиоматично; ^:0 означает "ничего не делать" и ^:1 означает "сделать один раз", поэтому цель ясна. @. лучше подходит для нетривиального поведения.

Во-вторых, используя & соединение "соединение / составление" значительно упрощает поезд. Повторное использование [: а также ] довольно запутанные и непрозрачные. Рефакторинг с использованием & объединяет связанные операции: сначала разделить n на две части, а именно n-2 а также n-1и, во-вторых, сложите fibn из этих двух чисел.

И наконец, "0 для обработки списка и M. для запоминания. M. является довольно важным с точки зрения производительности, так как прямая реализация канонического определения вызовет fib(2) чрезмерно. Вы можете получить свой торт (простое определение) и съесть его тоже (хорошая производительность) с помощью встроенного наречия напоминания.

Источник для этого конкретного определения: f0b на этой странице.

Answer 2

Хорошо, я нашел это. Я пропустил только рекурсивный блок через генератор молчания и получил этот блок.

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

Тогда я вставил это в оригинальную часть, получая это.

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

И это работает как шарм. Я тоже вставил " 0 до конца, чтобы заставить его принимать списки.