# Evaluate Conway chained arrow notation

## Background

Conway chained arrow notation is a notation to express very large numbers. It consists of zero or more positive integers separated by right arrows, e.g. $$\2 \to 3 \to 4 \to 5 \to 6 \$$.

Assuming $$\p, q, a_1, \dots, a_n\$$ are positive integers and $$\X\$$ is an abbreviation for a nonempty chain $$\a_1 \to a_2 \to \dots \to a_n\$$, the rules for evaluating such a notation are as follows:

\begin{align} (\text{empty chain}) &= 1 \\ (p) &= p \\ p \to q &= p^q \\ X \to 1 &= X \\ X \to 1 \to p &= X \\ X \to (p+1)\to (q+1) &= X \to (X \to p\to (q+1))\to q \end{align}

A length-3 chain has an equivalent up-arrow notation: $$\ p \to q \to r = p \uparrow^r q\$$.

Note that the arrow notation cannot be treated as some kind of binary operator:

\begin{align} 2 \to 3 \to 2 &= 16 \\ 2 \to (3 \to 2) &= 512 \\ (2 \to 3) \to 2 &= 64 \end{align}

Given a (possibly empty) list of positive integers, interpret it as Conway chained arrow notation and evaluate it into a single number.

It is OK if your program gives wrong answers for large values due to the limits (bounds and/or precision) of your language's number type, as long as the underlying algorithm is correct.

Standard rules apply. The shortest code in bytes wins.

## Test cases

Input => Output
[] => 1
[1] => 1
[99999999] => 99999999
[5, 5] => 3125
[4, 8] => 65536
[1, 2, 4] => 1
[2, 2, 4] => 4
[2, 3, 2] => 16
[2, 4, 2] => 65536
[4, 3, 2] => 4^256 = 1.34e154
[2, 2, 3, 2] => 4

• Can we take the input list in reversed order?
– Leo
Apr 29 '20 at 2:33
• @Leo Yes, no problem, as long as you state so in your answer. Apr 29 '20 at 2:59
• Interesting, but even after coding the algorithm, I feel I don't have any real insight into it. Did you read the original source? Does it have background on the intuition and motivation that led Conway to this definition? Apr 29 '20 at 4:18
• @Jonah There's a little motivation here. Apr 29 '20 at 7:05
• @MitchellSpector I looked it up in The Book of Numbers and the explanation there is pretty good: fundamentally, it looks like a generalization and more compact version of up arrow notation. Although all these things grow so fast they defy anything we have intuition about Apr 29 '20 at 11:36

f(q:p:x)|p^q>p,x>[]=f$q-1:f(q:p-1:x):x|1<2=f$p^q:x
f[x]=x
f _=1


Try it online!

Takes input as a list in reversed order, since in Haskell it's easier to deal with the beginning of a list than with the end of it.

Now shorter and uglier!

Rules 3,4,5,6 are combined in the first line. The most important trick is realizing that p^q==p iff p==1||q==1 (where ^ is exponentiation and we're dealing with strictly positive numbers). We check the conditions to apply rule 6 (p and q greater than 1, at least three elements in the input) and if they are valid we do so recursively. If these conditions fail we know that either there is a 1 in the first two elements or there are just two elements in total: for both of this cases f(p^q:x) can solve the task.

The last two lines deal with inputs with less than two elements. They could be rewritten as a single line f x=last$1:x but the score would not change. Below the original solution, no golfing tricks, just beautiful Haskell code: f[]=1 f[p]=p f[q,p]=p^q f(1:x)=f x f(_:1:x)=f x f(q:p:x)=f$q-1:f(q:p-1:x):x


Try it online!

• Haskell is just beautiful. Amazing that this syntax easily beats the dc and c "golfed" implementations.
– 6005
May 1 '20 at 14:07
• and aside of absence of whitespaces, it's actually not golfed at all. May 2 '20 at 5:08
• That's right, compared to "real" code this is just missing a type declaration and a more meaningful name for the function, so we could say my golfing was just removing comments and whitespace :D I'm a bit disappointed that I couldn't find a way to really golf this more, but I'm always happy to show how beautiful Haskell can be.
– Leo
May 2 '20 at 7:23
• Ok, sorry to ruin all of this, I found a way to golf it and made everything ugly :/
– Leo
May 2 '20 at 8:08

# dc, 112 107 bytes

?[dz0r^+q]sZ[rd3Rd_3R^q]sE[ilfx1rq]sA[iSplfx1rLprq]sB[z2>Zz2=Ed1=Ard1=B1-rlfx3RSpr1-lfx_3Rri1+Lp1+r3R]dsfxp


Try it online!

Or verify all the test cases.

The input is on stdin (a line with space-separated numbers), and the output is on stdout.

How it works:

dc is a stack-based language. The recursive macro f does the Conway chained-arrow calculation, but the stack is treated differently from what you usually see:

1. The input to f is the entire stack when the call is made. (So f essentially takes a variable number of arguments.)

2. If the stack at the time of call is

$$a_1 \; a_2 \; \dots \; a_n$$

(with the top of the stack on the right), f will compute the value of

$$a_1 \to a_2 \to \dots \to a_n$$

and push it on top of the stack, but it leaves the arguments on the stack also.

So f turns the stack

$$a_1 \; a_2 \; \dots \; a_n$$

into

$$a_1 \; a_2 \; \dots \; a_n \; [\text{ArrowValue}(a_1 \; a_2 \; \dots \; a_n)]$$

where I've written $$\\;[\text{ArrowValue}(a_1 \; a_2 \; \dots \; a_n)]\;\$$ for the value of $$\\;a_1 \to a_2 \to \dots \to a_n.\$$

There are several auxiliary macros as well. All the usual complex control structures other languages have (loops, conditionals, functions) are implemented in dc using macros.

Note that dc produces a few error messages or warnings due to the golfing tricks used, but they don't interrupt program execution, and the messages are just written to stderr. Examples of these: duplicating when there's nothing on the stack, adding when there's only one item on the stack, or setting the input base to an illegal value.

The code also makes use of the fact that we can distinguish positive numbers from $$\0\$$ by whether the power $$\0^x\$$ is $$\0\$$ or $$\1.\$$

Here's a detailed summary of the program's operation, updated for the revised, shorter answer.

?  Read a line of space-separated numbers, written in the usual
Conway chained-arrow order, pushing them onto the stack in turn.
(The chained arrow sequence will start at the bottom of the stack,
since that's pushed first, and will end at the top of the stack, since
that's pushed last.)

MACRO Z
Macro Z will only be called when the stack either is empty or
has just one item p on it.  We'll analyze both possibilities.
[   Start macro.
Stack: Empty   or   p
d    Duplicate.
Stack: Empty   or   p p
z    Push the size of the stack.
Stack: 0       or   p p 2
0    Push 0.
Stack: 0 0     or   p p 2 0
r
Swap.
Stack: 0 0     or   p p 0 2
^    Exponentiate.
Stack: 1       or   p p 0
+    Add top 2 items if they exist.
Stack: 1       or   p p
q    Exit this macro and the macro which called it.
]sZ End macro and name it Z.

Summary of Z:
Turn: Empty stack
Into: 1
and
Turn: p
into: p p

MACRO E
[       Start a macro.  Assume the stack is: ... p q (top on right).
r        Swap.                         Stack: ... q p
d        Duplicate.                    Stack: ... q p p
3R       Rotate left the top 3 items.  Stack: ... p p q
d        Duplicate.                    Stack: ... p p q q
_3R      Rotate right the top 3 items. Stack: ... p q p q
^        Exponentiate.                 Stack: ... p  q p**q
q        Exit this macro and the macro which called it.
]sE     End the macro and name it E.
Summary of E:
Turn: ... p q
into: ... p q p**q

MACRO A
[       Start a macro.  Assume the stack is:   ... p (top on right).
i        Discard the top of stack.  (Actually make it the new input radix just because dc wants a place to put it.)
Stack: ...
lfx      Call f recursively.           Stack: ... ArrowValue(...)
1        Push 1.                       Stack: ... ArrowValue(...) 1
r        Swap.                         Stack: ... 1 ArrowValue(...)
q        Exit this macro and the macro which called it.
]sA     End the macro and name it A.
Summary of A:
Turn: ... p
into: ... 1 ArrowValue(...)

MACRO B
[       Start a macro.  Assume the stack is:    ... p q (top on right).
i        Discard top of stack (by storing it as the input radix).
Stack: ... p
Sp       Pop p off the stack and
push it onto stack p.          Stack: ...
lfx      Call f recursively.            Stack: ... ArrowValue(...)
1        Push 1.                        Stack: ... ArrowValue(...) 1
r        Swap.                         Stack: ... 1 ArrowValue(...)
Lp       Pop the old value of p from stack p.
Stack: ... 1 ArrowValue(...) p
r        Swap                          Stack: ... 1 p ArrowValue(...)
q        Exit this macro and the macro which called it.
]sB     End the macro and name it B.
Summary of B:
Turn: ... p q
into: ... 1 p ArrowValue(...)

MACRO f
[       Start a macro.
z      Push the stack size.
2>     If the stack size was 0 or 1,
O        then call macro Z and return from f.
In this case, we've turned ...
into ... 1

or we've turned ... p
into ... p p

z2=E   If the stack size was 2,
then call macro E and return from f.
In this case, we've turned ... p q
into ... p q p**q

If we get here, the stack size is at least 3.

d1=A   If the item at the top of the stack == 1,
then call macro A and return from f.
In this case, we've turned ... 1
into ... 1 ArrowValue(...)

If we get here, the stack size is at least 3 and the item at the top of the stack isn't 1.
Stack: ... p q r
where r != 1.
r      Swap.                 Stack: ... p r q
d1=B   If the item at the top of the stack == 1,
then call macro B and return from f.
In this case, we've turned   ... p 1 r
into   ... p 1 r ArrowValue(... p)

If we get here, the stack size is at least 3, neither of the items at the top of the stack is 1,
Stack: ... p q r
to Stack: ... p r q
1-     Subtract 1.           Stack: ... p r q-1
r      Swap.                 Stack: ... p q-1 r
lfx    Call f recursively.   Stack: ... p q-1 r [ArrowValue(... p q-1 r)]
3R     Rotate left the top 3 items on the stack.
Stack: ... p r [ArrowValue(... p q-1 r)] q-1
Sp     Pop q-1 off the stack and push it onto stack p.
Stack: ... p r [ArrowValue(... p q-1 r)]
r      Swap.                 Stack: ... p [ArrowValue(... p q-1 r)] r
1-     Subtract 1.           Stack: ... p [ArrowValue(... p q-1 r)] r-1
lfx    Call f recursively.   Stack: ... p  [ArrowValue(... p q-1 r)]  r-1  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]
_3R    Rotate right the top 3 items on the stack.
Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  [ArrowValue(... p q-1 r)]  r-1
r      Swap:                 Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  r-1  [ArrowValue(... p q-1 r)]
i      Discard the top item. Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  r-1
1+     Add 1                 Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  r
Lp     Load the old value of q-1 from stack p.
Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  r  q-1
1+     Add 1.                Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  r  q
r      Swap.                 Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  q  r
3R     Rotate left the top 3 items on the stack.
Stack: ... p  q  r  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]
]       End the macro,
dsf       save it on the stack, and name it f.
Summary of f:
Turn: ...
into: ... ArrowValue(...)

x       Execute f.
p       Print the desired value, which is now at the top of the stack.


# C (gcc) -m32 -lm, 159150137 136 bytes

f(a,b,u,t)int*a,*b;{t=a-b?b-a-1?*a-1?b-a-2?a[1]-1?t=a[1]--,a[1]=f(a,b),--*a,u=f(a,b),++*a,a[1]=t,u:f(a+2,b):pow(a[1],*a):f(a+1,b):*a:1;}


Try the test cases online! (except for [4, 3, 2], which overflows).

9 bytes off thanks to ceilingcat!

And saved 1 more byte thanks to ceilingcat too.

Input is taken as an array of ints in reverse order, and is passed as a pointer to the beginning and a pointer to (the location immediately after) the end.

The following applies to the previous version of the program. The current version uses exponentiation from the C math library. The compilation flag -m32 is now used so that the usual #include <math.h> line can be omitted.

C doesn't have exponentiation built in, so the previous version handled that by changing the 3rd and 4th rules of the recursive definition from

\begin{align} p \to q &= p^q \\ X \to 1 &= X \\ \end{align}

to

\begin{align} \quad\quad\quad\quad\quad X \to 1 &= X \\ p \to q &= (p \to q-1)*p \\ \end{align}

• @ovs Thanks for fixing my mangled edit. Apr 30 '20 at 18:43

# APL (Dyalog Unicode), 574948 46 bytes

Saved 8 bytes thanks to @Bubbler!

{3>≢w←⍵↓⍨⊃⍸1≠⍵:*/⌽w⋄(∇(⊃w-1),,∘(2↓w))⍣(1⊃w)⊢1}


Try it online!

A monadic function that must be given the input in reverse. Now also requires zero-indexing. This is slightly different from Conway's definition, but I think it's equivalent. If anyone can find a more math-y proof, that'd be great.

This is how Conway described his chained arrow notation:

Our own "chained arrow" notation names some even larger numbers. In this, a^^...^^b (with c arrows) is called a->b->c.

a->b-> ... ->x->y-> 1 is another name for a->b-> ... ->x->y

and a ... x->y->(z+1) is defined to be

a ... x if y = 1,

a ... x->(a...x)->z if y = 2,

a ... x->(a...x->(a...x)->z)->z if y = 3

and so on.

No one likes ones (and $$\X\to 1\$$ evaluates to $$\X\$$), so we first remove leading ones using ⍵↓⍨⊃⍸1≠⍵. ⊃⍸1≠⍵ is the first (⊃) index where (⍸) there isn't a 1 (1≠⍵), and we drop (↓) until that index. The result of that is assigned to w to reuse.

We can replace the first rule from here with the first three rules from the question. So if w has 0, 1, or 2 elements (3>≢w), we can fold over it with exponentiation (*/⌽w), because according to APL's rules, */x is x and */⍬ (⍬ is an empty set) is 1. We do have to reverse (⌽) w again, though, because it was reversed in the first place.

The second part of the function takes care of cases when w is in the form $$\X \to y \to (z+1)\$$. It's essentially $$\y\$$ applications of the function $$\\lambda a. X \to a \to z\$$, starting, with 1.

If $$\y\$$ and $$\z\$$ are both 1, then this becomes $$\X \to 1 \to 1\$$. Next iteration, w will be just $$\X\$$. If only $$\y\$$ is 1, then it becomes $$\X \to 1 \to z\$$. After that, it becomes $$\X \to 1 \to (z-1)\$$, then $$\X \to 1 \to (z-2)\$$, and so on until it reaches $$\X \to 1 \to 1\$$, which gives us $$\X\$$. So this satisfies the fifth rule in the question ($$\X \to 1 \to p = X\$$).

If $$\y\$$ is greater than 1, this becomes $$X \to (X \to (... (X \to (X \to (1) \to z) \to z) ...) \to z) \to z\\ = X \to (X \to (... (X \to (X) \to z) ...) \to z) \text{ (by question's 5th rule)}$$ The second is Conway's definition (there are $$\y\$$ copies of $$\X\$$ and $$\y-1\$$ copies of $$\z\$$). In the first, there are $$\y\$$ copies of both $$\X\$$ and $$\z\$$.

• The second one doesn't work on TIO because you're using ⍤ as Atop (f⍤g) which was added in 18.0, while TIO is still at 17.1. You can convert that part into a train (eliminating the need of Atop). Also, 1 1, in */⌽1 1,⍵ can be entirely removed (*/⍬ is 1). Finally, using a variable for 2↓⍵ gives 49 bytes. Nov 25 '20 at 4:37

# J, 9079 75 bytes

(1:](^~/)(2&}.$:@,~<:@{.,[:$:]-2=#\)@.(3<.#))(\$:@}.~1+i.&1)@.(1 e.2&{.)


Try it online!

Takes input in reverse order.

I suspect there's room for more golfing yet. I may return to it tomorrow.

# Rust, 161 bytes

fn f(s:&[u32])->u32{match
s{[]=>1,[x]=>*x,[p,q]=>p.pow(*q),[x@..,1]=>f(x),[x@..,1,_]=>f(x),[x@..,p,q]=>f(&[x,&[f(&[x,&[p-1],&[*q]].concat())],&[q-1]].concat())}}


Uses Rusts pattern matching. The last case is a little verbose, because there's no spread operator.

Try it on the rust playground.

fn f(s: &[u32]) -> u32 {
match s {
[]=>1,
[x]=>*x,
[p,q]=>p.pow(*q),
[x@..,1]=>f(x),
[x@..,1,_]=>f(x),
[x@..,p,q]=>f(&[x, &[f(&[x,&[p-1,*q]].concat())], &[q-1]].concat())
}
}


# JavaScript (ES7),  78  77 bytes

Takes the list in reverse order.

f=([q,p,...a])=>a+a?f(--q?--p?[q,f([++q,p,...a]),...a]:a:[p,...a]):p**q||q||1


Try it online!

### With BigInt support (78 bytes)

This version accepts either a list of Numbers or a list of BigInts and returns a value of the same type.

f=([q,p,...a])=>a+a?f(--q?--p?[q,f([++q,p,...a]),...a]:a:[p,...a]):p?p**q:q||1


Try it online!

• Is that supposed to be a[0]? By my reading, that should be ...a...
– Neil
Apr 29 '20 at 10:00
• @Neil You're right: $X$ is ...a. Thank you! Apr 29 '20 at 10:11

# Python 2, 117112 111 bytes

f=lambda x:(len(x)<3)*reduce(lambda a,b:b**a,x,1)or f((1in x[:2])*x[1:]or[x[0]-1,f([x[0],x[1]-1]+x[2:])]+x[2:])


Try it online!

Takes input in reverse order.

A recursive function that takes in a list of positive integers and returns a single number.

In order to save bytes, we combine the 3 base cases into one expression:

(len(x)<3)*reduce(lambda a,b:b**a,x,1)


which returns either $$\1\$$, $$\p\$$, or $$\p^q\$$.

The recursive cases are also mashed together via:

f((1in x[:2])*x[1:]or[x[0]-1,f([x[0],x[1]-1]+x[2:])]+x[2:])


which becomes f(x[1:]) when x[0] is $$\1\$$ or x[1] is $$\1\$$, and becomes f([x[0]-1,f([x[0],x[1]-1]+x[2:])]+x[2:]) otherwise.

# Erlang (escript), 111 bytes

Port of the Haskell answer. The last case seems to time out.

f([])->1;f([P])->P;f([1|X])->f(X);f([Q,P])->math:pow(P,Q);f([_,1|X])->f(X);f([Q,P|X])->f([Q-1,f([Q,P-1|X])|X]).


Try it online!

# Factor, 144 bytes

:: g ( x -- y )
x llength 3 < [ x 1 [ swap ^ ] foldl ]
[ x car 1 = [ x cdr g ]
[ 1 x cadr [ x cdr cdr cons x car 1 - swons g ] times ] if
] if ;


Try it online!

Takes a linked list in reverse order. Uses the algorithm described in user's APL answer.

Using linked lists is shorter than using arrays when the code involves a lot of dissection at the start (and you don't need sophisticated sequence operations):

first (5)              > car (3)
rest (4)               > cdr (3)
second (6) > 1 nth (5) > cadr (4)
prefix (6)             > cons (4)
swap prefix (11)       > swons (5)
unclip (6)             = uncons (6)
unclip swap (11)       > unswons (7)


### How it works

:: g ( x -- y )         ! Takes a list x and returns a number
x llength 3 < [         ! If x has 2 or fewer numbers...
x 1 [ swap ^ ] foldl    ! Reduce by ^ on reversed arguments
] [                     ! Otherwise x is in the form of X->y->z
x car 1 = [           ! If z is 1...
x cdr g               ! Remove z(=1) and recurse
] [                   ! Otherwise...
1                     ! Setup the initial value of 1
x cadr                ! Setup the loop count of y
[ x cdr cdr cons      ! Build y':X
x car 1 - swons g ] ! Build z-1:y':X
times                 ! Iterate the above function y times to 1
] if
] if

• This paper's pretty interesting, although I don't know if it would be of any help.
– user
Feb 15 at 16:20

# 05AB1E, 68 66 bytes

"D©g2‹iPëi)Y.Vëi)Y.Vë)\®®g<imëX®šUs<s)Y.VXćsUDgÍsŠǝRć<šRY.V"DV.V


This was pretty hard in a stack-based language..

Explanation:

"                          "# Start a string we can execute as 05AB1E code
# to mimic recursive calls:
D                          # Duplicate the list at the top of the stack
# (which will be the (implicit) input at the start)
©                         # Store it in variable ® (without popping)
g2‹i                     # Pop one, and if its length is smaller than 2:
P                    #  Take the product
#  ([] → 1; [p] → p)
ë                        # Else (the length is >= 2):
                       #  Dump the contents of the list onto the stack
i                      #  Pop the top value, and if it's a 1:
)                     #   Wrap the remaining values into a list
Y.V                  #   And do a recursive call
#   (p=1 for [...,q,p] → recursive call to [...,q])
ë                      #  Else:
i                     #   Pop the second top value, and if it's a 1:
)                    #    Wrap the remaining values into a list
Y.V                 #    And do a recursive call
#    (q=1 for [...,q,p] → recursive call to [...])
ë                     #   Else:
)\                   #    Discard everything on the stack
®                 #    Dump the contents of ® onto the stack again
®g<i             #    If the length of ® is 2:
m            #     Take the power of the two values
#     ([p,q] → p^q)
ë             #    Else (the length is >= 3):
X®šU         #     Prepend ® to list X
#     (X is 1 by default, but that doesn't matter;
#      it'll become [[...,p,q],1] and the 1 is ignored)
s<s)         #     Decrease the second value from the top by 1
Y.V      #     And do a recursive call
#     ([...,p,q] → recursive call to [...,p-1,q],
#      let's call its result R for the moment)
Xć           #     Extract the first list from variable X again,
sU         #     and pop and store the remaining values as new X
DgÍ        #     Take its length - 2 (without popping by duplicating first)
#     (let's call this length-2 I for the moment)
sŠ      #     Swap & triple-swap ([...,R,[...,p,q],I] → [...,[...,p,q],R,I])
ǝ     #     Insert value R into the list at (0-based) index I
#     ([...,[...,p,q]] → [...,[...,R,q]])
Rć<šR      #     And decrease the last value in the top list by 1
#     ([...,[...,R,q]] → [...,[...,R,q-1]])
Y.V  #     And do a recursive call again
"                          "# End the string of 05AB1E code
DV                         # Store a copy of this string in variable Y
.V                       # Execute it as 05AB1E code (Y.V is how we can do recursive calls)
# (after which the result is output implicitly)


# Pyth, 40 38 bytes

L?tJtby?}1<b2J+,thby+,hbthJtJttb|^F_b1


Try it online!

Takes input in reverse order.

L defines a recursive function named y that takes in a list b of positive integers and returns a single number.

Similarly to my Python answer, the base cases are combined into one expression:

|^F_b1


in which ^F_b folds the exponentiation function ^ over b in reverse. If b has 2 elements $$\(q,p)\$$ this will return $$\p^q\$$, if b has 1 element $$\(p)\$$ it will return $$\p\$$, and if b is empty it will return 0 (| .. 1 turns the 0 into 1, as needed)

The recursive cases are handled by:

y?}1<b2J+,thby+,hbthJtJttb


This part is a pretty straightforward translation of the recursive rules. If either of the first two elements of b are 1 it calls y on tb (equivalent to b[1:] in Python)*. Otherwise, the formula $$\X \to (X \to p\to (q+1))\to q\$$ is passed recusively to y.

*The rule $$\X \to 1 \to p = X\$$ thus takes two steps instead of one, but doing it this way saves a few bytes.

# Java, 282 chars

interface c{int n[]=new int[99];static void main(String[]a){int i=0,j=a.length;for(;i<j;)n[i]=new Integer(a[i++]);System.out.print(j<1?1:j<2?n[0]:c(j));}static int c(int j){j-=n[j-2]<2?2:n[j-1]<2?1:0;if(j<3)return(int)Math.pow(n[0],n[1]);n[j-2]--;n[j-2]=c(j);n[j-1]--;return c(j);}}


interface c{
int n[]=new int[99];
static void main(String[]a){
int i=0,j=a.length;for(;i<j;)n[i]=new Integer(a[i++]);
System.out.print(j<1?1:j<2?n[0]:c(j));
}
static int c(int j){
j-=n[j-2]<2?2:n[j-1]<2?1:0;
if(j<3)return(int)Math.pow(n[0],n[1]);
n[j-2]--;
n[j-2]=c(j);
n[j-1]--;
return c(j);
}
}


# Clojure, 117 bytes

(defn f([]1)([q]q)([q p](Math/pow p q))([q p & x](if(== p(f q p))(apply f p x)(apply f(dec q)(apply f q(dec p)x)x))))


Try it online!

Handles all test cases, takes input arguments in reverse order.

# Wolfram Language (Mathematica), 67 66 bytes

f[x__,1,_:0]=f@x
f[x___,p_:1,q_:1]=If[x<1,p^q,f[x,f[x,p-1,q],q-1]]


Try it online!

# Scala, 156 141 bytes

val f:Seq[Int]=>Int={case x if x.size<3=>(x:\1.0)(math.pow(_,_))toInt
case 1::x=>f(x)case p::1::x=>f(x)case q::p::x=>f(q-1::f(q::p-1::x)::x)}


Try it in Scastie

Note: Input must be a reversed List. If it's not reversed, the algorithm won't work correctly, and if it's not a List, there'll be a MatchError.

I hate that math.pow(_,_) works but just math.pow would need the first argument to be a Double.