Функция Аккермана известна тем, что является одним из простейших примеров полной вычислимой функции, которая не является примитивно-рекурсивной.

Мы будем использовать определение A(m,n)взятия двух неотрицательных целых чисел, где

A(0,n) = n+1
A(m,0) = A(m-1,1)
A(m,n) = A(m-1,A(m,n-1))

Вы можете реализовать

• именованная или анонимная функция, принимающая в качестве входных данных два целых числа, возвращающая целое число, или
• программа, получающая два целых числа, разделенных пробелом или новой строкой, в STDIN и выводит результат в STDOUT.

Вы не можете использовать функцию Аккермана или функцию гиперэкспонирования из библиотеки, если она существует, но вы можете использовать любую другую функцию из любой другой библиотеки. Допускается регулярное возведение в степень.

Ваша функция должна быть в состоянии найти значение A(m,n)для m ≤ 3 и n ≤ 10 менее чем за минуту. Он должен, по крайней мере, теоретически завершаться на любых других входах: учитывая бесконечное пространство стека, собственный тип Bigint и произвольно длительный период времени, он будет возвращать ответ. Изменить: Если ваш язык имеет глубину рекурсии по умолчанию, которая слишком ограничительна, вы можете перенастроить ее без затрат на символы.

Представление с кратчайшим количеством символов выигрывает.

Вот некоторые значения, чтобы проверить ваш ответ:

  A  | n=0     1     2     3     4     5     6     7     8     9    10
-----+-----------------------------------------------------------------
 m=0 |   1     2     3     4     5     6     7     8     9    10    11
   1 |   2     3     4     5     6     7     8     9    10    11    12
   2 |   3     5     7     9    11    13    15    17    19    21    23
   3 |   5    13    29    61   125   253   509  1021  2045  4093  8189
   4 |  13 65533   big   really big...

Пиф , 19

DaGHR?atG?aGtHH1GhH

Определяет a, который работает как функция Аккермана. Обратите внимание, что для этого требуется более высокая глубина рекурсии, чем допускал до сегодняшнего дня официальный компилятор pyth a 3 10, поэтому я увеличил глубину рекурсии. Это не изменение языка, просто компилятор.

Тест:

$ time pyth -c "DaGHR?atG?aGtHH1GhH           ;a 3 10"
8189

real    0m0.092s
user    0m0.088s
sys     0m0.000s

Объяснение:

DaGH                     def a(G,H):
    R                    return
    ?          G                (if G:
     atG                              (a(G-1,
        ?    H                               (if H:
         aGtH                                      a(G,H-1)
              1                               else:1)
                hH               else:H+1)

По сути, это в первую очередь обусловливает значение истинности того, Gследует ли возвращать или возвращать H + 1. Если он рекурсивный, первым аргументом всегда является G-1, и он Hзависит от значения истинности того , использовать ли его в a(G,H-1)качестве второго аргумента или использовать 1в качестве второго аргумента.

Хаскелл, 35

0%n=1+n
m%n=iterate((m-1)%)1!!(n+1)

это определяет функцию оператора %.

это работает, заметив , что m%n(где aфункция Аккермана) для ненулевых mв (m-1)%прикладной n+1раз 1. например, 3%2определяется как 2%(3%1)что есть 2%(2%(3%0)), а это2%(2%(2%1))

GolfScript (30)

{1$1>{1\){1$(\A}*\;}{+)}if}:A;

Онлайн демо

Без 1>(каких особых случаев A(1, n)) вычисление A(3, 10)на компьютере, на котором я его тестировал, занимает 9 минут . В этом особом случае достаточно быстро, чтобы онлайн-демонстрация заняла менее 10 секунд.

Обратите внимание, что это не наивный перевод определения. Глубина рекурсии ограничена m.

рассечение

{             # Function boilerplate
  1$          # Get a copy of m: stack holds m n m
  1>{         # (Optimisation): if m is greater than 1
    1         #   Take this as the value of A(m, -1)
    \){       #   Repeat n+1 times:
              #     Stack: m A(m, i-1)
      1$(\    #     Stack: m m-1 A(m, i-1)
      A       #     Stack: m A(m, i)
    }*
    \;        #   Lose that unwanted copy of m
  }{          # Else
    +)        #   A(m in {0, 1}, n) = m + n + 1
  }if
}:A;          # Function boilerplate

Двоичное лямбда-исчисление , 54 бита = 6,75 байта

HexDump:

00000000: 1607 2d88 072f 68                        ..-../h

Binary:

000101100000011100101101100010000000011100101111011010

Это λ м . m (λ g . λ n . g ( n g 1)) (λ n . λ f . λ x . f ( n f x )), где все числа представлены в виде церковных чисел .

JavaScript, ES6, 41 34 байта

f=(m,n)=>m?f(m-1,!n||f(m,n-1)):n+1

Запустите это на последней консоли Firefox, и она создаст функцию, fкоторую вы можете вызывать с различными значениями mи nт.п.

f(3,2) // returns 29

ИЛИ

попробуйте код ниже в последнем Firefox

f=(m,n)=>m?f(m-1,!n||f(m,n-1)):n+1

B.onclick=_=>alert(f(+M.value, +N.value))

#M,#N{max-width:15px;border: 1px solid;border-width:0 0 1px 0}

<div>f(<input id=M />,<input id=N />)</div><br><button id=B>Evaluate</button>

Python 2.7.8 - 80, 54, 48, 46 45

A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n

(Кредиты для XNOR!)

Более читаемый, но с еще одним символом:

A=lambda m,n:n+(m<1or A(m-1,n<1or A(m,n-1))-n)

Не то, чтобы я должен был установить sys.setrecursionlimit(10000), чтобы получить результат для A(3,10). Дальнейшая игра в гольф с использованием логической индексации не работала из-за резко растущей глубины рекурсии.

J - 26 символов

($:^:(<:@[`]`1:)^:(0<[)>:)

Существует альтернативное, более функциональное определение Аккермана:

Ack 0 n = n+1
Ack m n = Iter (Ack (m-1)) n
Iter f 0 = f 1
Iter f n = f (Iter f (n-1))

Бывает так, что Iterочень легко написать в J, потому что J имеет способ передачи в m-1to, Ackа также для определения начального значения, равного Iter1. Объясняется взрывом:

(                      >:)  NB. increment n
                ^:(0<[)     NB. if m=0, do nothing to n+1; else:
   ^:                       NB. iterate...
($:                      )  NB.   self ($: is recursion)
     (<:@[     )            NB.   with left arg m-1
          `]                NB.   n+1 times
            `1:             NB.   starting on 1

Это опирается на то, что J называет формой ^:герунда - по сути, способ иметь больший контроль над всеми границами молчаливым (бессмысленным) способом.

На REPL:

   3 ($:^:(<:@[`]`1:)^:(0<[)>:) 3
61
   ack =: ($:^:(<:@[`]`1:)^:(0<[)>:)
   (i.4) ack"0 table (i.11)
+-----+------------------------------------------+
|ack"0|0  1  2  3   4   5   6    7    8    9   10|
+-----+------------------------------------------+
|0    |1  2  3  4   5   6   7    8    9   10   11|
|1    |2  3  4  5   6   7   8    9   10   11   12|
|2    |3  5  7  9  11  13  15   17   19   21   23|
|3    |5 13 29 61 125 253 509 1021 2045 4093 8189|
+-----+------------------------------------------+
   6!:2 '3 ($:^:(<:@[`]`1:)^:(0<[)>:) 10'  NB. snugly fits in a minute
58.5831

Нам нужно определить ackпо имени, чтобы иметь возможность поместить его в таблицу, потому что $:это ужасный, уродливый зверь, который набрасывается на любого, кто пытается это понять. Это самореференция, где «я» определяется как самая большая глагольная фраза, содержащая его. tableэто наречие, и поэтому хотелось бы стать частью фразы глагола, если вы дадите ему возможность, поэтому вы должны поймать $:в ловушку названное определение, чтобы использовать его.

Изменить: 24 символа?

Спустя годы я нашел решение, которое на два символа короче.

(0&<~(<:@#~$:/@,1:^:)>:)

Это намного медленнее, хотя: 3 ack 8занимает больше минуты на моей машине. Это потому, что (1) я использую сгиб /вместо итерации, поэтому J, вероятно, должен запомнить больше вещей, чем обычно, и (2), в то время как 0&<~выполняет те же вычисления (0<[), что и, фактически, получает n+1время выполнения, прежде чем предпринимать рекурсивный шаг при вызове m ack n- 0&<происходит быть идемпотентом, чтобы не испортить расчет, но nбыстро набрать обороты и стать ackочень рекурсивным.

Я сомневаюсь, что более мощная машина может выдвинуть новый код менее чем за минуту, потому что это компьютер, где старый код может найти 3 ack 10менее чем за 15 секунд.

C - 41 байт

Ничего особенного - небольшие пределы означают, что все необходимые значения могут быть вычислены менее чем за 1 секунду, наивно следуя определению функции.

A(m,n){return!m?n+1:A(m-1,n?A(m,n-1):1);}


int main()
{
    int m,n;
    for(m = 0; m <= 3; m++)
    for(n = 0; n <= 10; n++)
    printf("%d %d %d\n", m,n,A(m,n));
    return 0;
}

Javascript ES6 (34)

a=(m,n)=>m?a(m-1,n?a(m,n-1):1):n+1

Реализация:

a=(m,n)=>m?a(m-1,n?a(m,n-1):1):n+1

td[colspan="2"] input{width: 100%;}

<table><tbody><tr><td>m=</td><td><input id="m" type="number" value="0" /></td></tr><tr><td>n=</td><td><input id="n" type="number" value="0" /></td></tr><tr><td colspan="2"><input type="button" value="Calculate!" onclick="document.getElementById('out').value=a(document.getElementById('m').value, document.getElementById('n').value)" /></td></tr><tr><td colspan="2"><input id="out" disabled="disabled" type="text" /></td></tr></tbody></table>

JavaScript (ES6) - 34

A=(m,n)=>m?A(m-1,!n||A(m,n-1)):n+1

И тест:

> A=(m,n)=>m?A(m-1,!n||A(m,n-1)):n+1;s=new Date().getTime();console.log(A(3,10),(new Date().getTime() - s)/1000)
8189 16.441

Coq, 40

nat_rec _ S(fun _ b n=>nat_iter(S n)b 1)

Это функция типа nat -> nat -> nat. Поскольку Coq допускает только построение полных функций, оно также служит формальным доказательством того, что повторение Аккермана является обоснованным.

Демо-версия:

Welcome to Coq 8.4pl6 (November 2015)

Coq < Compute nat_rec _ S(fun _ b n=>nat_iter(S n)b 1) 3 10.
     = 8189
     : nat

Примечание: Coq 8.5, выпущенный после этого испытания, переименован nat_iterв Nat.iter.

Ракетка 67

(define(a m n)(if(= m 0)(+ n 1)(a(- m 1)(if(= n 0)1(a m(- n 1))))))

Mathematica, 46 байтов

0~a~n_:=n+1
m_~a~n_:=a[m-1,If[n<1,1,a[m,n-1]]]

Занимает ровно минуту a[3,10]. Обратите внимание, что предел рекурсии по умолчанию в Mathematica слишком мал a[3,8]и ниже (по крайней мере, на моем компьютере), но это можно исправить, настроив

$RecursionLimit = Infinity

Javascript с лямбдами, 34

A=(m,n)=>m?A(m-1,n?A(m,n-1):1):n+1

Типичный ответ, не может сделать что-нибудь короче.

Haskell, 48 44 символов (36 для списка)

Хотя это решение не такое короткое, как у другого решения на Haskell, оно примечательно тем, что оно выражает функцию Аккермана в виде бесконечного списка, который, я думаю, выглядит довольно аккуратно. Результатом является бесконечный список (из бесконечных списков), такой что в позиции [m, n] он содержит значение A (m, n) .

Сам бесконечный список:

iterate(tail.(`iterate`1).(!!))[1..]

Как функция (для соответствия спецификации):

i=iterate;m%n=i(tail.(`i`1).(!!))[1..]!!m!!n

Формулировка была получена путем наблюдения, что общий / общий случай для функции Аккермана состоит в том, чтобы использовать значение слева в качестве индекса в строке выше. Базовый случай для этой рекурсии (т. Е. Самый левый столбец строки, т. Е. A (m, 0) ) заключается в использовании второго крайнего левого значения в строке выше. Базовый случай для этой рекурсии - это случай A (0, n) = n + 1 , то есть первая строка [1..].

Таким образом, мы получаем

let a0 = [1..]
let a1 = tail $ iterate (a0 !!) 1  -- 'tail' because iterate starts by applying
let a2 = tail $ iterate (a1 !!) 1  -- the function 0 times
-- etc

Затем мы просто добавляем еще один уровень итерации на основе этого паттерна и делаем бессмысленное жонглирование.

Крошечный Лисп , 70 (вне конкуренции)

Это выходит за рамки конкуренции, так как язык новее, чем вопрос, и он также не может выполнить то, (A 3 10)что требуется в вопросе, из-за переполнения стека.

(d A(q((m n)(i m(i n(A(s m 1)(A m(s n 1)))(A(s m 1)1))(s n(s 0 1))))))

Это определяет функцию, Aкоторая вычисляет функцию Аккермана. отформатирован:

(d A
   (q( (m n)
       (i m
          (i n
             (A (s m 1)
                (A m
                   (s n 1)
                 )
              ) 
             (A (s m 1)
                1
              )
           )
          (s n
             (s 0 1)
           )
        )
    ) )
 )

Мы используем все встроенные макросы ( d(define) и q(quote) и i(if)) и одну встроенную функцию ( s- вычитание) здесь.

i выполняет свою истинную часть, когда условием является число> 0 (а в противном случае - ложная часть), поэтому здесь не нужно делать явное сравнение.

sявляется единственной доступной арифметической операцией, мы используем ее как для n-1/ m-1, так и (s n (s 0 1))для n+1.

Tiny lisp использует оптимизацию хвостовой рекурсии, но это помогает только для внешнего Aвызова в результате, но не для A(m, n-1)вызова, который используется для параметров.

С моей крошечной реализацией lisp в Ceylon на JVM она работает (A 3 5) = 253, но кажется, что она ломается при попытке (A 2 125)прямого вычисления (что должно дать тот же результат). Если после этого вычислить (A 3 4) = 125, то JVM, похоже, должен оптимизировать функции настолько, чтобы встроить некоторые промежуточные вызовы функций в моем интерпретаторе, обеспечивая большую глубину рекурсии. Странный.

Эталонная реализация вытворяет , (A 3 5) = 253а также (A 2 163) = 329, но не удается (A 2 164), и поэтому даже меньше (A 3 6) = (A 2 253).

Go, 260 243 240 122 байт

Я не видел, чтобы этот вопрос позволял анонсировать.

далеко не конкурентоспособный, но я изучаю этот язык, и я хотел проверить это.

func (m,n int)int{r:=0
switch{case m==0&&n!=0:r=n+1
case m!=0&&n==0:r=a(m-1,1)
case m!=0&&n!=0:r=a(m-1,a(m,n-1))}
return r}

используйте его как, go run ack.goа затем укажите два числа, mи n. если m> 4 или n> 30, время выполнения может превышать полминуты.

для m=3 n=11:

$ time go run ack
16381
real    0m1.434s
user    0m1.432s
sys     0m0.004s

править : сохранено всего 17 байт, переключаясь на switchболее if/elseи дот-импорт

Haskell: 81 69 байт

a::Int->Int->Int
a 0 n=n+1
a m 0=a (m-1) 1
a m n=a (m-1) a m (n-1)

a 3 10 занимает около 45 секунд.

(неконкурентный) Pyth, 15 байтов

M?GgtG?HgGtH1hH

Попробуйте онлайн! (пример использования g3Tдобавленной функции , что означает g(3,10))

(неконкурентный) UGL , 31 30 байт

iiRuldr%l%lR$d%rd:u%d:%+uRu:ro

Ввод разделен переводом строки.

Попробуйте онлайн!

(Это было реализовано в качестве стандартного примера в интерпретаторе.)

Юлия, 34 31 28 байт

m\n=m>0?~-m\(n<1||m\~-n):n+1

Это именованная анонимная функция. Это прямая реализация рекурсивного определения, злоупотребляющая способностью Юлии переопределять операторы .

Попробуйте онлайн!

R - 54 52

Я использовал это в качестве предлога, чтобы попытаться разобраться в R, так что это, вероятно, действительно плохо сделано :)

a=function(m,n)"if"(m,a(m-1,"if"(n,a(m,n-1),1)),n+1)

Пример запуска

> a(3,8)
[1] 2045

Я получаю переполнение стека для чего-либо кроме этого

T-SQL- 222

Я думал, что я попытаюсь заставить T-SQL сделать это также. Использовал другой метод, потому что рекурсия не так хороша в SQL. Что-нибудь более 4,2 бомб это.

DECLARE @m INT=4,@n INT=1;WITH R AS(SELECT 2 C, 1 X UNION ALL   SELECT POWER(2,C),X+1FROM R)SELECT IIF(@m=0,@n+1,IIF(@m=1,@n+2,IIF(@m=2,2*@n+3,IIF(@m=3,POWER(2,@n+3)-3,IIF(@m=4,(SELECT TOP(1)C FROM R WHERE x= @n+3)-3,-1)))))

мозговой трах , 90 байтов

>>>>+>,>,<<[>[>[-[->>>+<<<]<[->+>>+<<<]>-[-<+>]>+>>>>>]<[->+>>]]<[>>+[-<<<+>>>]<<-]<<<]>>.

Попробуйте онлайн!

Предполагается реализация с произвольным размером ячейки, с IO в качестве чисел. -6 байт, если вы не возражаете против использования отрицательных ячеек.

Заканчивается примерно через 30 секунд для 3,8 в связанном интерпретаторе, если вы отметили правильные настройки. Введите введенные числа с добавлением \s, например, 3,9is \3\9.

Tcl , 67 байт

proc tcl::mathfunc::A m\ n {expr {$m?A($m-1,$n?A($m,$n-1):1):$n+1}}

Попробуйте онлайн!

proc A m\ n {expr {$m?[A [expr $m-1] [expr {$n?[A $m [expr $n-1]]:1}]]:$n+1}}

Попробуйте онлайн!

В онлайн-компиляторе он не запускается из-за истечения времени ожидания, но в локальном интерпретаторе Tcl он работает хорошо. Я профилировал каждый корневой вызов Aфункции, чтобы увидеть, сколько времени заняло вычисление для каждой пары, {m,n}подлежащей тестированию:

m=0, n=0, A=1, time=3.5e-5 seconds
m=0, n=1, A=2, time=2e-6 seconds
m=0, n=2, A=3, time=8e-6 seconds
m=0, n=3, A=4, time=1e-6 seconds
m=0, n=4, A=5, time=2e-6 seconds
m=0, n=5, A=6, time=1e-6 seconds
m=0, n=6, A=7, time=1e-6 seconds
m=0, n=7, A=8, time=1e-6 seconds
m=0, n=8, A=9, time=1e-6 seconds
m=0, n=9, A=10, time=0.0 seconds
m=0, n=10, A=11, time=1e-6 seconds
m=1, n=0, A=2, time=4e-6 seconds
m=1, n=1, A=3, time=6e-6 seconds
m=1, n=2, A=4, time=1e-5 seconds
m=1, n=3, A=5, time=1.2e-5 seconds
m=1, n=4, A=6, time=1.5e-5 seconds
m=1, n=5, A=7, time=2e-5 seconds
m=1, n=6, A=8, time=2e-5 seconds
m=1, n=7, A=9, time=2.6e-5 seconds
m=1, n=8, A=10, time=3e-5 seconds
m=1, n=9, A=11, time=3e-5 seconds
m=1, n=10, A=12, time=3.3e-5 seconds
m=2, n=0, A=3, time=8e-6 seconds
m=2, n=1, A=5, time=2.2e-5 seconds
m=2, n=2, A=7, time=3.9e-5 seconds
m=2, n=3, A=9, time=6.3e-5 seconds
m=2, n=4, A=11, time=9.1e-5 seconds
m=2, n=5, A=13, time=0.000124 seconds
m=2, n=6, A=15, time=0.000163 seconds
m=2, n=7, A=17, time=0.000213 seconds
m=2, n=8, A=19, time=0.000262 seconds
m=2, n=9, A=21, time=0.000316 seconds
m=2, n=10, A=23, time=0.000377 seconds
m=3, n=0, A=5, time=2.2e-5 seconds
m=3, n=1, A=13, time=0.000145 seconds
m=3, n=2, A=29, time=0.000745 seconds
m=3, n=3, A=61, time=0.003345 seconds
m=3, n=4, A=125, time=0.015048 seconds
m=3, n=5, A=253, time=0.059836 seconds
m=3, n=6, A=509, time=0.241431 seconds
m=3, n=7, A=1021, time=0.971836 seconds
m=3, n=8, A=2045, time=3.908884 seconds
m=3, n=9, A=4093, time=15.926341 seconds
m=3, n=10, A=8189, time=63.734713 seconds

Не удается для последней пары {m,n}={3,10} , поскольку это занимает немного больше чем одна минута.

Для более высоких значений m, то необходимо будет увеличить recursionlimitзначение.

Я могу сократить его до 65 байт, но он не будет отвечать требованию вопроса «Ваша функция должна быть способна найти значение A (m, n) для m ≤ 3 и n ≤ 10 менее чем за минуту». Без{} этого тайм-аут на TIO и не делать демо из последних двух записей.

Tcl , 65 байт

proc tcl::mathfunc::A m\ n {expr $m?A($m-1,$n?A($m,$n-1):1):$n+1}

Попробуйте онлайн!

J: 50

>:@]`(1$:~<:@[)`(<:@[$:[$:_1+])@.(0>.[:<:@#.,&*)M.

Возвращает в доли секунды для 0 ... 3 против 0 ... 10:

   A=:>:@]`(1$:~<:@[)`(<:@[$:[$:_1+])@.(0>.[:<:@#.,&*)M.
   timespacex 'res=:(i.4) A"0 table (i.11)'
0.0336829 3.54035e6
   res
┌───┬──────────────────────────────────────────┐
│A"0│0  1  2  3   4   5   6    7    8    9   10│
├───┼──────────────────────────────────────────┤
│0  │1  2  3  4   5   6   7    8    9   10   11│
│1  │2  3  4  5   6   7   8    9   10   11   12│
│2  │3  5  7  9  11  13  15   17   19   21   23│
│3  │5 13 29 61 125 253 509 1021 2045 4093 8189│
└───┴──────────────────────────────────────────┘

PS: «0 служит для того, чтобы заставить A работать с каждым отдельным элементом, вместо того, чтобы сожрать левый и правый массив и генерировать ошибки длины. Но это не требуется, например, для 9 = 2 A 3.

APL, 31

{⍺=0:⍵+1⋄⍵=0:1∇⍨⍺-1⋄(⍺-1)∇⍺∇⍵-1}

Довольно просто. Использует символ once один раз, чтобы сохранить один байт путем обращения аргументов. Принимает m в качестве левого аргумента и n в качестве правого аргумента.

TryAPL.org

Руби, 65

h,a={},->m,n{h[[m,n]]||=m<1?(n+1):(n<1?a[m-1,1]:a[m-1,a[m,n-1]])}

объяснение

Это довольно простой перевод алгоритма, приведенного в описании проблемы.

• Входные данные принимаются в качестве аргументов лямбды. IntegerОжидается два с.
• Для ускорения и избежания ошибок переполнения стека ответы запоминаются в Hash h. ||=Оператор используется для вычисления значения , которое не было ранее вычисленным.

a[3,10] рассчитывается в ~ 0,1 сек на моей машине.

Вот не разгромленная версия

h = {}
a = lambda do |m,n|
  h[[m,n]] ||= if m < 1 
    n + 1
  elsif n < 1
    a[m-1,1]
  else
    a[m-1,a[m,n-1]]
  end
end

Мышь-2002 , 99 83 байта

$Y1%j:j.0=m:2%k:k.0=n:m.n.>[k.1+!|m.n.<[#Y,j.1-,1;|m.n.*0=[#Y,j.1-,#Y,j.,k.1+;;]]]@

Java, 274 байта

import java.math.*;class a{BigInteger A(BigInteger b,BigInteger B){if(b.equals(BigInteger.ZERO))return B.add(BigInteger.ONE);if(B.equals(BigInteger.ZERO))return A(b.subtract(BigInteger.ONE),BigInteger.ONE);return A(b.subtract(BigInteger.ONE),A(b,B.subtract(BigInteger.ONE)));}}

Он рассчитывает A(3,10)за несколько секунд, и, учитывая бесконечное пространство памяти и стека, он может рассчитывать любую комбинацию bи Bдо тех пор, пока результат будет ниже 2 ^2147483647 -1.

Цейлон, 88 87 85

alias I=>Integer;I a(I m,I n)=>m<1then n+1else(n<1then a(m-1,1)else a(m-1,a(m,n-1)));

Это простая реализация. отформатирован:

alias I => Integer;
I a(I m, I n) =>
        m < 1
        then n + 1
        else (n < 1
            then a(m - 1, 1)
            else a(m - 1, a(m, n - 1)));

Псевдоним сохраняет только один байт, без него (с записью Integerвместо I) мы получили бы до 86 байт. Еще два байта можно сохранить, заменив == 0их < 1дважды.

С настройками по умолчанию ceylon run, он будет работать до A(3,12) = 32765(и A(4,0) = 13), но A(3,13)(и, следовательно, также A(4,1)) выдаст ошибку переполнения стека. ( A(3,12)занимает около 5 секунд,A(3,11) около 3 на моем компьютере.)

Использование ceylon run-js(то есть выполнение результата компиляции в JavaScript на node.js) происходит намного медленнее (требуется 1 мин 19 с A(3,10)) и прерывается уже A(3, 11)с «Превышен максимальный размер стека вызовов» (с использованием настроек по умолчанию) после запуска для 1 мин 30 с.

Цейлон без рекурсии, 228

В качестве бонуса, это нерекурсивная версия (конечно, более длинная, но не подверженная переполнению стека - может в какой-то момент получить ошибку нехватки памяти).

import ceylon.collection{A=ArrayList}Integer a(Integer[2]r){value s=A{*r};value p=s.addAll;while(true){if(exists m=s.pop()){if(exists n=s.pop()){if(n<1){p([m+1]);}else if(m<1){p([n-1,1]);}else{p([n-1,n,m-1]);}}else{return m;}}}}

отформатирован:

import ceylon.collection {
    A=ArrayList
}

Integer a(Integer[2] r) {
    value s = A { *r };
    value p = s.addAll;
    while (true) {
        if (exists m = s.pop()) {
            if (exists n = s.pop()) {
                if (n < 1) {
                    p([m + 1]);
                } else if (m < 1) {
                    p([n - 1, 1]);
                } else {
                    p([n - 1, n, m - 1]);
                }
            } else {
                // stack is empty
                return m;
            }
        }
    }
}

На моем компьютере он работает намного медленнее, чем рекурсивная версия: A(3,11)занимает 9,5 секунды, A(3,12)34 секунды, A(3,13)2:08 минуты,A(3,14) 8:25 минут. (У меня изначально была версия, использующая ленивые итерации вместо имеющихся у меня кортежей, которая была даже намного медленнее, с тем же размером).

Немного быстрее (21 секунда A(3,12)) (но также на один байт длиннее) - версия, использующая s.pushвместо s.addAll, но ее нужно вызывать несколько раз, чтобы добавить несколько чисел, поскольку для каждого требуется только одно целое число. Использование LinkedList вместо ArrayList намного медленнее.