La fonction Ackermann est remarquable pour être l’un des exemples les plus simples d’une fonction totale calculable qui n’est pas récursive primitive.

Nous allons utiliser la définition de la A(m,n)prise en deux entiers non négatifs où

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

Vous pouvez implémenter

• une fonction nommée ou anonyme prenant deux entiers en entrée, renvoyant un entier, ou
• un programme prenant deux entiers séparés par une ligne ou un espace sur STDIN, en imprimant un résultat vers STDOUT.

Vous ne pouvez pas utiliser une fonction Ackermann ou une fonction d'hyperexponentiation d'une bibliothèque, s'il en existe une, mais vous pouvez utiliser toute autre fonction d'une autre bibliothèque. Une exponentiation régulière est autorisée.

Votre fonction doit pouvoir trouver la valeur de A(m,n)pour m ≤ 3 et n ≤ 10 en moins d'une minute. Il doit au moins théoriquement se terminer par toute autre entrée: avec un espace de pile infini, un type Bigint natif et une période de temps arbitrairement longue, la réponse sera renvoyée. Éditer: Si votre langue a une profondeur de récursion par défaut trop restrictive, vous pouvez la reconfigurer sans frais de caractères.

La soumission avec le plus petit nombre de caractères gagne.

Voici quelques valeurs pour vérifier votre réponse:

  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...

Pyth , 19

DaGHR?atG?aGtHH1GhH

Définit ace qui fonctionne comme la fonction Ackermann. Notez que cela nécessite une profondeur de récursion supérieure à celle calculée par le compilateur pyth officiel jusqu'à ce jour a 3 10, donc j'ai augmenté la profondeur de récursivité. Ce n'est pas un changement de langage, mais uniquement pour le compilateur.

Tester:

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

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

Explication:

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)

Essentiellement, il conditionne d'abord la valeur de vérité, Gqu'il s'agisse de récidiver ou de renvoyer H + 1. S'il est récurrent, le premier argument est toujours G-1 et conditionne la valeur de vérité, à Hsavoir s'il doit être utilisé a(G,H-1)comme second argument ou s'il doit être utilisé 1comme second argument.

Haskell, 35 ans

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

ceci définit la fonction d'opérateur %.

cela fonctionne en remarquant que m%n(où aest la fonction ackerman) mest (m-1)%appliqué à des n+1temps différents de zéro 1. par exemple, 3%2est défini comme 2%(3%1)ce qui est 2%(2%(3%0)), et c'est2%(2%(2%1))

GolfScript (30)

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

Démo en ligne

Sans le 1>(cas particuliers A(1, n)), A(3, 10)le calcul sur l'ordinateur sur lequel je l'ai testé prend 9 minutes . Avec ce cas spécial, il est assez rapide que la démonstration en ligne prenne moins de 10 secondes.

Notez que ce n'est pas une traduction naïve de la définition. La profondeur de récursivité est délimitée par m.

Dissection

{             # 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

Calcul lambda binaire , 54 bits = 6,75 octets

Hexdump:

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

Binaire:

000101100000011100101101100010000000011100101111011010

C'est λ m . m (λ g . λ n . g ( n g 1)) (λ n . λ f . λ x . f ( n f x )), où tous les nombres sont représentés par des chiffres Eglise .

JavaScript, ES6, 41 à 34 octets

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

Exécutez ceci dans une dernière console de Firefox et cela créera une fonction appelée fque vous pouvez appeler avec différentes valeurs de mand nlike

f(3,2) // returns 29

OU

essayez le code ci-dessous dans un dernier 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

(Crédits à xnor!)

Plus lisible, mais avec 1 caractère supplémentaire:

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

Non pas que je devais régler sys.setrecursionlimit(10000)pour obtenir un résultat A(3,10). La poursuite de la pratique du golf à l'aide d'une indexation logique n'a pas fonctionné en raison de la profondeur de plus en plus grande de la récursion.

J - 26 caractères

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

Il existe une autre définition, plus fonctionnelle, d’Ackermann:

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))

Il se trouve qu’il Iterest très facile d’écrire en J, parce que J a le moyen de transmettre le m-1à Acket de définir la valeur initiale de Iter1. Expliqué par explosion:

(                      >:)  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

Cela repose sur ce que J appelle la forme générale de ^:- un moyen fondamental d'avoir plus de contrôle sur toutes les limites de manière tacite (sans point).

Au 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

Nous devons définir ackpar nom pour pouvoir le mettre dans un tableau, car $:c'est une bête horrible et laide qui frappe furieusement tous ceux qui tentent de le comprendre. C'est une référence à soi, où self est défini comme la phrase du verbe le plus grand qui la contient. tableest un adverbe et aimerait donc faire partie de la phrase du verbe si vous lui en donnez la chance. Vous devez donc vous en tenir $:à une définition nommée pour l'utiliser.

Edit: 24 caractères?

Des années plus tard, j'ai trouvé une solution composée de deux caractères plus courts.

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

C'est beaucoup plus lent, cependant: cela 3 ack 8prend plus d'une minute avec ma machine. C'est parce que (1) j'utilise un repli /au lieu de l'itération, donc J doit probablement se rappeler plus de choses que d'habitude, et (2) tout en 0&<~effectuant le même calcul que (0<[), il est en réalité exécuté plusieurs n+1fois avant de passer à l'étape récursive lors de l'appel m ack n- 0&<cela se produit être idempotent, cela ne gâche donc pas le calcul, mais ndevient rapide et acktrès récursif.

Je doute qu'une machine plus puissante puisse afficher le nouveau code en moins d'une minute, car il s'agit d'un ordinateur sur lequel l'ancien code peut être trouvé 3 ack 10en moins de 15 secondes.

C - 41 octets

Rien à faire - les petites limites signifient que toutes les valeurs requises peuvent être calculées en moins de 1 seconde en suivant naïvement la définition de la fonction.

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

La mise en oeuvre:

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

Et un test:

> 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)

C'est une fonction de type nat -> nat -> nat. Coq n'autorisant que la construction de fonctions globales, il sert également de preuve formelle du bien-fondé de la récurrence d'Ackermann.

Démo:

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

Note: Coq 8.5, publié après ce défi, renommé nat_iterpour Nat.iter.

Raquette 67

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

Mathematica, 46 octets

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

Prend à peu près exactement une minute pour a[3,10]. Notez que la limite de récursivité par défaut de Mathematica est trop petite pour a[3,8]et au-delà (du moins sur ma machine), mais cela peut être corrigé en configurant

$RecursionLimit = Infinity

Javascript avec lambdas, 34

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

Une réponse typique, ne peut rien raccourcir.

Haskell, 48 44 caractères (36 pour la liste)

Bien que n'étant pas aussi courte que l'autre solution Haskell, celle-ci est remarquable car elle exprime la fonction Ackermann sous la forme d'une liste infinie, ce qui, à mon avis, est plutôt génial. Le résultat est une liste infinie (de listes infinies) telle que, à la position [m, n] elle contienne la valeur A (m, n) .

La liste infinie elle-même:

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

En fonction (pour se conformer à la spécification):

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

La formulation a été dérivée en observant que le cas général / commun de la fonction Ackermann consiste à utiliser la valeur à gauche comme index dans la ligne ci-dessus. Le cas de base de cette récursivité (c'est-à-dire la colonne la plus à gauche d'une ligne, c'est-à-dire A (m, 0) ) consiste à utiliser la deuxième valeur la plus à gauche de la ligne ci-dessus. Le cas de base pour cela récurrence est le cas A (0, n) = n + 1 , c'est-à-dire que la première ligne est [1..].

Ainsi, nous obtenons

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

Ensuite, nous ajoutons simplement un autre niveau d'itération basé sur ce modèle et faisons des jongles inutiles .

Tiny Lisp , 70 ans (hors compétition)

Ceci est hors compétition, car le langage est plus récent que la question et ne réussit pas non plus à exécuter le (A 3 10)code requis dans la question, en raison d'un débordement de pile.

(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))))))

Ceci définit une fonction Aqui calcule la fonction Ackermann. Formaté:

(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)
           )
        )
    ) )
 )

Nous utilisons toutes les macros internes ( d(définir) et q(quote) et i(if)) et une fonction intégrée (s - soustraire) ici.

i exécute sa vraie partie quand la condition est un nombre> 0 (sinon la fausse partie), nous n'avons donc pas à faire de comparaison explicite ici.

sest la seule opération arithmétique disponible, nous l’utilisons pour le n-1/ m-1, ainsi que(s n (s 0 1)) pour n+1.

Lisp minuscule utilise l'optimisation de la récursion de la queue, mais cela n'aide que pour l'extérieur A appel dans le résultat, pas pour l' A(m, n-1)appel utilisé pour les paramètres.

Avec ma toute petite implémentation de lisp à Ceylan sur la machine virtuelle, cela fonctionne (A 3 5) = 253, mais il semble s’effondrer lorsque je tente de calculer(A 2 125) directement (ce qui devrait donner le même résultat). En calculant cela après (A 3 4) = 125, la JVM semble avoir suffisamment optimisé les fonctions pour intégrer des appels de fonction intermédiaires dans mon interpréteur, ce qui permet une plus grande profondeur de récursivité. Étrange.

L' implémentation de référence se lève pour (A 3 5) = 253et aussi (A 2 163) = 329, mais ne réussit pas (A 2 164), et donc encore moins (A 3 6) = (A 2 253).

Go, 260 243 240 122 octets

Je n'ai pas vu que la question permettait anon funcs.

loin d'être compétitif, mais j'apprends cette langue et je voulais le tester.

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}

utilisez-le comme go run ack.goet ensuite fournissez deux nombres, metn . si m> 4 ou n> 30, le temps d'exécution peut être supérieur à une demi-minute.

pour m=3 n=11:

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

edit : total enregistré 17 octets en passant aux importations de switchsur if/elseet de points

Haskell: 81 69 octets

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 prend environ 45 secondes.

Pyth (non concurrent), 15 octets

M?GgtG?HgGtH1hH

Essayez-le en ligne! (exemple d'utilisation de la fonction g3Tajoutée, ce qui signifie g(3,10))

UGL (non concurrent) , 31 à 30 octets

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

Entrée séparée par des nouvelles lignes.

Essayez-le en ligne!

(Il a été implémenté comme exemple standard dans l'interpréteur.)

Julia, 34 31 28 octets

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

C'est une fonction anonyme nommée. C'est une implémentation directe de la définition récursive, abusant de la capacité de Julia à redéfinir les opérateurs .

Essayez-le en ligne!

R - 54 52

J'ai utilisé cela comme une excuse pour essayer de comprendre R, alors c'est probablement très mal fait :)

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

Exemple d'exécution

> a(3,8)
[1] 2045

Je reçois un débordement de pile pour quoi que ce soit au-delà

T-SQL- 222

Je pensais que j'essaierais de faire en sorte que T-SQL le fasse également. Utilisé une méthode différente parce que la récursivité n'est pas très agréable en SQL. Tout ce qui dépasse 4,2 le bombe.

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)))))

brainfuck , 90 octets

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

Essayez-le en ligne!

Suppose une implémentation avec une taille de cellule de taille arbitraire, avec IO en tant que nombres. -6 octets si cela ne vous dérange pas d'utiliser des cellules négatives.

Termine en environ 30 secondes pour 3,8 dans l’interprète lié, à condition de cocher les paramètres appropriés. Tapez les nombres entrés précédés de \s, par exemple 3,9est \3\9.

Tcl , 67 octets

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

Essayez-le en ligne!

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

Essayez-le en ligne!

Dans le compilateur en ligne, son exécution échoue, mais dans un interpréteur Tcl local, il fonctionne bien. Je me suis profilé de chaque appel racine à Afonction, pour voir combien de temps le calcul a pris pour chaque paire de {m,n}sujets à tester:

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

Cela échoue pour la dernière paire {m,n}={3,10}, car cela prend un peu plus d'une minute.

Pour des valeurs plus élevées de m, il sera nécessaire d'augmenter la recursionlimitvaleur.

Je ne peux pas l'obtenir plus court à 65 octets, mais cela ne répondra pas à l'exigence de la question "Votre fonction doit pouvoir trouver la valeur de A (m, n) pour m ≤ 3 et n ≤ 10 en moins d'une minute.". Sans {}cela, le délai d'attente sur TIO sera dépassé et la démonstration des deux dernières entrées ne sera pas effectuée.

Tcl , 65 octets

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

Essayez-le en ligne!

J: 50

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

Revient en une fraction de seconde pour 0 ... 3 vs 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: le "0 sert à faire un travail sur chaque élément, au lieu de dévorer les tableaux gauche et droit, et de générer des erreurs de longueur. Mais ce n'est pas nécessaire pour, par exemple, 9 = 2 A 3.

APL, 31

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

Assez simple. Utilise le caractère une fois pour sauvegarder un octet en inversant les arguments. Prend m comme argument de gauche et n comme argument de droite.

TryAPL.org

Ruby, 65 ans

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

Explication

Ceci est une traduction assez simple de l'algorithme donné dans la description du problème.

• L'entrée est considérée comme l'argument d'un lambda. DeuxInteger s sont attendus.
• Pour plus de rapidité et pour éviter les erreurs de débordement de pile, les réponses sont mémorisées dans le Hash h. le||= opérateur est utilisé pour calculer une valeur qui n'avait pas été calculée auparavant.

a[3,10] est calculé en ~ 0.1 secondes sur ma machine.

Voici une version non-golfée

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

Mouse-2002 , 99 83 octets

$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 octets

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)));}}

Il calcule A(3,10)en quelques secondes, et compte tenu de l'espace mémoire et de la pile infinis, il peut calculer n'importe quelle combinaison de bet Baussi longtemps que le résultat est inférieur à 2 ^2147483647 -1.

Ceylan, 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)));

Ceci est une implémentation simple. Formaté:

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)));

L'alias enregistre un seul octet, sans lui (avec l'écriture Integerau lieu de I), nous aurions 86 octets. Deux autres octets peuvent être sauvegardés en les remplaçant == 0par < 1deux fois.

Avec les paramètres par défaut de ceylon run, cela fonctionnera jusqu’à A(3,12) = 32765(et A(4,0) = 13), mais A(3,13)(et donc aussi A(4,1)) jettera une erreur de débordement de pile. ( A(3,12)prend environ 5 secondes, A(3,11)environ 3 sur mon ordinateur.)

Utiliser ceylon run-js(c.-à-d. Exécuter le résultat de la compilation en JavaScript sur node.js) est beaucoup plus lent (nécessite 1 min 19 s A(3,10)), et fonctionne déjà A(3, 11)avec une »Taille maximale de la pile d'appels dépassée« (avec les paramètres par défaut) après une exécution de 1 min 30 s.

Ceylan sans récursivité, 228

En bonus, voici une version non-récursive (plus longue, bien sûr, mais à l'abri des débordements de pile - peut provoquer une erreur d'insuffisance de mémoire à un moment donné).

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;}}}}

Formaté:

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;
            }
        }
    }
}

Il est assez lent sur mon ordinateur que la version récursive: A(3,11)prend 9,5 secondes, A(3,12)prend 34 secondes, A(3,13)prend 2:08 minutes, A(3,14)prend 8:25 minutes. (J'avais initialement une version utilisant des iterables paresseux au lieu des tuples que j'ai maintenant, qui était même beaucoup plus lente, avec la même taille).

Un peu plus rapide (21 secondes pour A(3,12)) (mais aussi un octet plus) est une version en utilisant au s.pushlieu de s.addAll, mais qui devait être appelé à plusieurs reprises pour ajouter plusieurs numéros, car il faut un seul entier chacun. L'utilisation d'une LinkedList au lieu d'une ArrayList est beaucoup plus lente.