Repository: algorand/pyteal

Issue:
Simplify recursive subroutine calling in TEAL 5
## Summary
TEAL 5 introduces the [`cover` and `uncover` opcodes](https://github.com/algorand/go-algorand/pull/2541) for stack manipulation, which can be used to greatly reduce the amount of opcodes and stack space needed to implement recursive subroutine calling.

## Scope
Instead of using `dig` and `pop` to help spill scratch slots during a potentially recursive subroutine call in `spillLocalSlotsDuringRecursion`, `cover` and `uncover` can do a better job. There are comments in this section of code describing the exact improvements that can be made: https://github.com/algorand/pyteal/blob/1157c57a66205bd7aa24390fe2d0254fbf609872/pyteal/compiler/subroutines.py#L119-L167

Currently 

## Priority
Not strictly needed, but this is a worthwhile improvement for subroutines.

Discussion:

Patch:
diff --git a/docs/byte_expression.rst b/docs/byte_expression.rst
index 52e2e95..acc5355 100644
--- a/docs/byte_expression.rst
+++ b/docs/byte_expression.rst
@@ -29,12 +29,33 @@ example:
 Substring Extraction
 --------------------
 
-Byte slices can be extracted from other byte slices using the :any:`Substring` expression. This
-expression can extract part of a byte slicing given start and end indices. For example:
+Byte slices can be extracted from other byte slices using the :any:`Substring` and :any:`Extract`
+expressions. These expressions are extremely similar, except one specifies a substring by start and
+end indexes, while the other uses a start index and length. Use whichever makes sense for your
+application.
+
+Substring
+~~~~~~~~~
+
+The :any:`Substring` expression can extract part of a byte slice given start and end indices. For
+example:
+
+.. code-block:: python
+
+    Substring(Bytes("algorand"), Int(2), Int(8)) # will produce "gorand"
+
+Extract
+~~~~~~~
+
+.. note::
+    :code:`Extract` is only available in TEAL version 5 or higher.
+
+The :any:`Extract` expression can extract part of a byte slice given the start index and length. For
+example:
 
 .. code-block:: python
 
-    Substring(Bytes("algorand"), Int(0), Int(4)) # will produce "algo"
+    Extract(Bytes("algorand"), Int(2), Int(6)) # will produce "gorand"
 
 Manipulating Individual Bits and Bytes
 --------------------------------------
diff --git a/pyteal/ast/__init__.py b/pyteal/ast/__init__.py
index a131142..157623b 100644
--- a/pyteal/ast/__init__.py
+++ b/pyteal/ast/__init__.py
@@ -82,10 +82,13 @@ from .binaryexpr import (
     BytesLe,
     BytesGt,
     BytesGe,
+    ExtractUint16,
+    ExtractUint32,
+    ExtractUint64,
 )
 
 # ternary ops
-from .ternaryexpr import Ed25519Verify, Substring, SetBit, SetByte
+from .ternaryexpr import Ed25519Verify, Substring, Extract, SetBit, SetByte
 
 # more ops
 from .naryexpr import NaryExpr, And, Or, Concat
@@ -184,6 +187,7 @@ __all__ = [
     "GetByte",
     "Ed25519Verify",
     "Substring",
+    "Extract",
     "SetBit",
     "SetByte",
     "NaryExpr",
@@ -224,6 +228,9 @@ __all__ = [
     "BytesGe",
     "BytesNot",
     "BytesZero",
+    "ExtractUint16",
+    "ExtractUint32",
+    "ExtractUint64",
     "Log",
     "While",
     "For",
diff --git a/pyteal/ast/binaryexpr.py b/pyteal/ast/binaryexpr.py
index c3ecbf4..28bf436 100644
--- a/pyteal/ast/binaryexpr.py
+++ b/pyteal/ast/binaryexpr.py
@@ -1,6 +1,7 @@
 from typing import Union, Tuple, cast, TYPE_CHECKING
 
 from ..types import TealType, require_type
+from ..errors import verifyTealVersion
 from ..ir import TealOp, Op, TealBlock
 from .expr import Expr
 
@@ -34,6 +35,12 @@ class BinaryExpr(Expr):
         self.argRight = argRight
 
     def __teal__(self, options: "CompileOptions"):
+        verifyTealVersion(
+            self.op.min_version,
+            options.version,
+            "TEAL version too low to use op {}".format(self.op),
+        )
+
         return TealBlock.FromOp(
             options, TealOp(self, self.op), self.argLeft, self.argRight
         )
@@ -517,3 +524,72 @@ def BytesGe(left: Expr, right: Expr) -> BinaryExpr:
         right: Must evaluate to bytes.
     """
     return BinaryExpr(Op.b_ge, TealType.bytes, TealType.uint64, left, right)
+
+
+def ExtractUint16(string: Expr, offset: Expr) -> BinaryExpr:
+    """Extract 2 bytes (16 bits) and convert them to an integer.
+
+    The bytes starting at :code:`offset` up to but not including :code:`offset + 2` will be
+    interpreted as a big-endian unsigned integer.
+
+    If :code:`offset + 2` exceeds :code:`Len(string)`, the program fails.
+
+    Requires TEAL version 5 or higher.
+
+    Args:
+        string: The bytestring to extract from. Must evaluate to bytes.
+        offset: The offset in the bytestring to start extracing. Must evaluate to uint64.
+    """
+    return BinaryExpr(
+        Op.extract_uint16,
+        (TealType.bytes, TealType.uint64),
+        TealType.uint64,
+        string,
+        offset,
+    )
+
+
+def ExtractUint32(string: Expr, offset: Expr) -> BinaryExpr:
+    """Extract 4 bytes (32 bits) and convert them to an integer.
+
+    The bytes starting at :code:`offset` up to but not including :code:`offset + 4` will be
+    interpreted as a big-endian unsigned integer.
+
+    If :code:`offset + 4` exceeds :code:`Len(string)`, the program fails.
+
+    Requires TEAL version 5 or higher.
+
+    Args:
+        string: The bytestring to extract from. Must evaluate to bytes.
+        offset: The offset in the bytestring to start extracing. Must evaluate to uint64.
+    """
+    return BinaryExpr(
+        Op.extract_uint32,
+        (TealType.bytes, TealType.uint64),
+        TealType.uint64,
+        string,
+        offset,
+    )
+
+
+def ExtractUint64(string: Expr, offset: Expr) -> BinaryExpr:
+    """Extract 8 bytes (64 bits) and convert them to an integer.
+
+    The bytes starting at :code:`offset` up to but not including :code:`offset + 8` will be
+    interpreted as a big-endian unsigned integer.
+
+    If :code:`offset + 8` exceeds :code:`Len(string)`, the program fails.
+
+    Requires TEAL version 5 or higher.
+
+    Args:
+        string: The bytestring to extract from. Must evaluate to bytes.
+        offset: The offset in the bytestring to start extracing. Must evaluate to uint64.
+    """
+    return BinaryExpr(
+        Op.extract_uint64,
+        (TealType.bytes, TealType.uint64),
+        TealType.uint64,
+        string,
+        offset,
+    )
diff --git a/pyteal/ast/ternaryexpr.py b/pyteal/ast/ternaryexpr.py
index d409f97..2e34fb2 100644
--- a/pyteal/ast/ternaryexpr.py
+++ b/pyteal/ast/ternaryexpr.py
@@ -1,6 +1,7 @@
 from typing import Tuple, TYPE_CHECKING
 
 from ..types import TealType, require_type
+from ..errors import verifyTealVersion
 from ..ir import TealOp, Op, TealBlock
 from .expr import Expr
 
@@ -32,6 +33,12 @@ class TernaryExpr(Expr):
         self.thirdArg = thirdArg
 
     def __teal__(self, options: "CompileOptions"):
+        verifyTealVersion(
+            self.op.min_version,
+            options.version,
+            "TEAL version too low to use op {}".format(self.op),
+        )
+
         return TealBlock.FromOp(
             options, TealOp(self, self.op), self.firstArg, self.secondArg, self.thirdArg
         )
@@ -73,13 +80,16 @@ def Ed25519Verify(data: Expr, sig: Expr, key: Expr) -> TernaryExpr:
 def Substring(string: Expr, start: Expr, end: Expr) -> TernaryExpr:
     """Take a substring of a byte string.
 
-    Produces a new byte string consisting of the bytes starting at start up to but not including
-    end.
+    Produces a new byte string consisting of the bytes starting at :code:`start` up to but not
+    including :code:`end`.
+
+    This expression is similar to :any:`Extract`, except this expression uses start and end indexes,
+    while :code:`Extract` uses a start index and length.
 
     Args:
         string: The byte string.
         start: The starting index for the substring. Must be an integer less than or equal to
-            Len(string).
+            :code:`Len(string)`.
         end: The ending index for the substring. Must be an integer greater or equal to start, but
             less than or equal to Len(string).
     """
@@ -93,6 +103,33 @@ def Substring(string: Expr, start: Expr, end: Expr) -> TernaryExpr:
     )
 
 
+def Extract(string: Expr, start: Expr, length: Expr) -> TernaryExpr:
+    """Extract a section of a byte string.
+
+    Produces a new byte string consisting of the bytes starting at :code:`start` up to but not
+    including :code:`start + length`.
+
+    This expression is similar to :any:`Substring`, except this expression uses a start index and
+    length, while :code:`Substring` uses start and end indexes.
+
+    Requires TEAL version 5 or higher.
+
+    Args:
+        string: The byte string.
+        start: The starting index for the extraction. Must be an integer less than or equal to
+            :code:`Len(string)`.
+        length: The number of bytes to extract. Must be an integer such that :code:`start + length <= Len(string)`.
+    """
+    return TernaryExpr(
+        Op.extract3,
+        (TealType.bytes, TealType.uint64, TealType.uint64),
+        TealType.bytes,
+        string,
+        start,
+        length,
+    )
+
+
 def SetBit(value: Expr, index: Expr, newBitValue: Expr) -> TernaryExpr:
     """Set the bit value of an expression at a specific index.
 
diff --git a/pyteal/compiler/compiler.py b/pyteal/compiler/compiler.py
index 804f618..1644e83 100644
--- a/pyteal/compiler/compiler.py
+++ b/pyteal/compiler/compiler.py
@@ -217,7 +217,7 @@ def compileTeal(
     )
 
     spillLocalSlotsDuringRecursion(
-        subroutineMapping, subroutineGraph, localSlotAssignments
+        version, subroutineMapping, subroutineGraph, localSlotAssignments
     )
 
     subroutineLabels = resolveSubroutines(subroutineMapping)
diff --git a/pyteal/compiler/subroutines.py b/pyteal/compiler/subroutines.py
index 496f820..a9f8064 100644
--- a/pyteal/compiler/subroutines.py
+++ b/pyteal/compiler/subroutines.py
@@ -62,6 +62,7 @@ def findRecursionPoints(
 
 
 def spillLocalSlotsDuringRecursion(
+    version: int,
     subroutineMapping: Dict[Optional[SubroutineDefinition], List[TealComponent]],
     subroutineGraph: Dict[SubroutineDefinition, Set[SubroutineDefinition]],
     localSlots: Dict[Optional[SubroutineDefinition], Set[int]],
@@ -75,6 +76,7 @@ def spillLocalSlotsDuringRecursion(
     slots from being modifying by a new recursive invocation of the current subroutine.
 
     Args:
+        version: The current TEAL version being assembled.
         subroutineMapping: A dictionary containing a list of TealComponents for every subroutine in
             a program. The key None is taken to indicate the main program routine. This input may be
             modified by this function in order to spill subroutine slots.
@@ -87,6 +89,8 @@ def spillLocalSlotsDuringRecursion(
     """
     recursivePoints = findRecursionPoints(subroutineGraph)
 
+    coverAvailable = version >= Op.cover.min_version
+
     for subroutine, reentryPoints in recursivePoints.items():
         slots = list(sorted(slot for slot in localSlots[subroutine]))
         numArgs = subroutine.argumentCount()
@@ -108,63 +112,89 @@ def spillLocalSlotsDuringRecursion(
                 # restore the local slots after returning from the subroutine. This prevents a
                 # reentry into the current subroutine from modifying variables we are currently
                 # using.
+
+                digArgs = True
+                coverSpilledSlots = False
+                uncoverArgs = False
+                if coverAvailable:
+                    digArgs = False
+                    if len(slots) < numArgs:
+                        coverSpilledSlots = True
+                    else:
+                        uncoverArgs = True
+
                 for slot in slots:
                     # spill local slots to the stack
                     before.append(TealOp(None, Op.load, slot))
 
+                    if coverSpilledSlots:
+                        # numArgs is guaranteed to be at least 2 here (since numArgs > len(slots)
+                        # and len(slots) must be at least 1 for the code to get this far), so no
+                        # need to replace this with swap if numArgs is 1
+                        before.append(TealOp(None, Op.cover, numArgs))
+
                 for _ in range(numArgs):
                     # pull the subroutine arguments to the top of the stack, above the just spilled
-                    # local slots
-
-                    # TODO: TEAL 5+, do this instead:
-                    # before.append(TealOp(None, Op.uncover, len(slots)))
-                    # or just do cover during the previous loop where slots are loaded, whichever
-                    # is more efficient
-                    before.append(
-                        TealOp(
-                            None,
-                            Op.dig,
-                            len(slots) + subroutine.argumentCount() - 1,
+                    # local slots, if needed
+
+                    stackDistance = len(slots) + numArgs - 1
+
+                    if uncoverArgs:
+                        if stackDistance == 1:
+                            before.append(TealOp(None, Op.swap))
+                        else:
+                            before.append(TealOp(None, Op.uncover, stackDistance))
+
+                    if digArgs:
+                        before.append(
+                            TealOp(
+                                None,
+                                Op.dig,
+                                stackDistance,
+                            )
                         )
-                    )
-                    # because we are stuck using dig instead of uncover in TEAL 4, we'll need to
-                    # pop all of the dug up arguments after the function returns
+                        # because we are stuck using dig instead of uncover in TEAL 4, we'll need to
+                        # pop all of the dug up arguments after the function returns
 
-                preserveReturnValue = False
+                hideReturnValueInFirstSlot = False
 
                 if subroutine.returnType != TealType.none:
                     # if the subroutine returns a value on the stack, we need to preserve this after
                     # restoring all local slots.
-                    preserveReturnValue = True
-                    if len(slots) > 1:
-                        # Store the return value into slots[0] temporarily. As an optimization, if
-                        # len(slots) == 1 we can just do a single swap instead
-                        after.append(TealOp(None, Op.store, slots[0]))
 
-                    # TODO: TEAL 5+, just do cover len(slots), so after restoring all slots the
-                    # return value is on top of the stack
+                    if len(slots) == 1:
+                        after.append(TealOp(None, Op.swap))
+                    elif coverAvailable:
+                        after.append(TealOp(None, Op.cover, len(slots)))
+                    else:
+                        # Store the return value into slots[0] temporarily
+                        hideReturnValueInFirstSlot = True
+                        after.append(TealOp(None, Op.store, slots[0]))
 
                 for slot in slots[::-1]:
                     # restore slots, iterating in reverse because slots[-1] is at the top of the stack
-                    if preserveReturnValue and slot is slots[0]:
+                    if hideReturnValueInFirstSlot and slot is slots[0]:
                         # time to restore the return value to the top of the stack
-                        if len(slots) > 1:
-                            # slots[0] is being used to store the return value, so load it again
-                            after.append(TealOp(None, Op.load, slot))
+
+                        # slots[0] is being used to store the return value, so load it again
+                        after.append(TealOp(None, Op.load, slot))
+
                         # swap the return value with the actual value of slot[0] on the stack
                         after.append(TealOp(None, Op.swap))
+
                     after.append(TealOp(None, Op.store, slot))
 
-                for _ in range(numArgs):
-                    # clear out the duplicate arguments that were dug up previously, since dig
-                    # does not pop the dug values -- once we use cover/uncover to properly set up
-                    # the spilled slots, this will no longer be necessary
-                    if subroutine.returnType != TealType.none:
-                        # if there is a return value on top of the stack, we need to preserve
-                        # it, so swap it with the subroutine argument that's below it on the
-                        # stack
-                        after.append(TealOp(None, Op.swap))
-                    after.append(TealOp(None, Op.pop))
+                if digArgs:
+                    for _ in range(numArgs):
+                        # clear out the duplicate arguments that were dug up previously, since dig
+                        # does not pop the dug values -- once we use cover/uncover to properly set up
+                        # the spilled slots, this will no longer be necessary
+                        if subroutine.returnType != TealType.none:
+                            # if there is a return value on top of the stack, we need to preserve
+                            # it, so swap it with the subroutine argument that's below it on the
+                            # stack
+                            after.append(TealOp(None, Op.swap))
+                        after.append(TealOp(None, Op.pop))
 
             newOps += before
             newOps.append(stmt)


Test patch:
diff --git a/pyteal/ast/binaryexpr_test.py b/pyteal/ast/binaryexpr_test.py
index 84d6f93..9602be2 100644
--- a/pyteal/ast/binaryexpr_test.py
+++ b/pyteal/ast/binaryexpr_test.py
@@ -5,7 +5,10 @@ from .. import *
 # this is not necessary but mypy complains if it's not included
 from .. import CompileOptions
 
-options = CompileOptions()
+teal2Options = CompileOptions(version=2)
+teal3Options = CompileOptions(version=3)
+teal4Options = CompileOptions(version=4)
+teal5Options = CompileOptions(version=5)
 
 
 def test_add():
@@ -17,7 +20,7 @@ def test_add():
         [TealOp(args[0], Op.int, 2), TealOp(args[1], Op.int, 3), TealOp(expr, Op.add)]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -39,7 +42,7 @@ def test_add_overload():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -64,7 +67,7 @@ def test_minus():
         [TealOp(args[0], Op.int, 5), TealOp(args[1], Op.int, 6), TealOp(expr, Op.minus)]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -86,7 +89,7 @@ def test_minus_overload():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -111,7 +114,7 @@ def test_mul():
         [TealOp(args[0], Op.int, 3), TealOp(args[1], Op.int, 8), TealOp(expr, Op.mul)]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -133,7 +136,7 @@ def test_mul_overload():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -158,7 +161,7 @@ def test_div():
         [TealOp(args[0], Op.int, 9), TealOp(args[1], Op.int, 3), TealOp(expr, Op.div)]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -180,7 +183,7 @@ def test_div_overload():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -205,7 +208,7 @@ def test_mod():
         [TealOp(args[0], Op.int, 10), TealOp(args[1], Op.int, 9), TealOp(expr, Op.mod)]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -227,7 +230,7 @@ def test_mod_overload():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -252,12 +255,15 @@ def test_exp():
         [TealOp(args[0], Op.int, 2), TealOp(args[1], Op.int, 9), TealOp(expr, Op.exp)]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_exp_overload():
     args = [Int(2), Int(3), Int(1)]
@@ -275,13 +281,16 @@ def test_exp_overload():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     with TealComponent.Context.ignoreExprEquality():
         assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_exp_invalid():
     with pytest.raises(TealTypeError):
@@ -312,7 +321,7 @@ def test_arithmetic():
         ]
     )
 
-    actual, _ = v.__teal__(options)
+    actual, _ = v.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -333,7 +342,7 @@ def test_bitwise_and():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -355,7 +364,7 @@ def test_bitwise_and_overload():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -384,7 +393,7 @@ def test_bitwise_or():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -406,7 +415,7 @@ def test_bitwise_or_overload():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -435,7 +444,7 @@ def test_bitwise_xor():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -457,7 +466,7 @@ def test_bitwise_xor_overload():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -482,12 +491,15 @@ def test_shift_left():
         [TealOp(args[0], Op.int, 5), TealOp(args[1], Op.int, 1), TealOp(expr, Op.shl)]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_shift_left_overload():
     args = [Int(5), Int(1), Int(2)]
@@ -504,13 +516,16 @@ def test_shift_left_overload():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     with TealComponent.Context.ignoreExprEquality():
         assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_shift_left_invalid():
     with pytest.raises(TealTypeError):
@@ -529,12 +544,15 @@ def test_shift_right():
         [TealOp(args[0], Op.int, 5), TealOp(args[1], Op.int, 1), TealOp(expr, Op.shr)]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_shift_right_overload():
     args = [Int(5), Int(1), Int(2)]
@@ -551,13 +569,16 @@ def test_shift_right_overload():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     with TealComponent.Context.ignoreExprEquality():
         assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_shift_right_invalid():
     with pytest.raises(TealTypeError):
@@ -580,7 +601,7 @@ def test_eq():
         ]
     )
 
-    actual_int, _ = expr_int.__teal__(options)
+    actual_int, _ = expr_int.__teal__(teal2Options)
     actual_int.addIncoming()
     actual_int = TealBlock.NormalizeBlocks(actual_int)
 
@@ -598,7 +619,7 @@ def test_eq():
         ]
     )
 
-    actual_bytes, _ = expr_bytes.__teal__(options)
+    actual_bytes, _ = expr_bytes.__teal__(teal2Options)
     actual_bytes.addIncoming()
     actual_bytes = TealBlock.NormalizeBlocks(actual_bytes)
 
@@ -618,7 +639,7 @@ def test_eq_overload():
         ]
     )
 
-    actual_int, _ = expr_int.__teal__(options)
+    actual_int, _ = expr_int.__teal__(teal2Options)
     actual_int.addIncoming()
     actual_int = TealBlock.NormalizeBlocks(actual_int)
 
@@ -636,7 +657,7 @@ def test_eq_overload():
         ]
     )
 
-    actual_bytes, _ = expr_bytes.__teal__(options)
+    actual_bytes, _ = expr_bytes.__teal__(teal2Options)
     actual_bytes.addIncoming()
     actual_bytes = TealBlock.NormalizeBlocks(actual_bytes)
 
@@ -664,7 +685,7 @@ def test_neq():
         ]
     )
 
-    actual_int, _ = expr_int.__teal__(options)
+    actual_int, _ = expr_int.__teal__(teal2Options)
     actual_int.addIncoming()
     actual_int = TealBlock.NormalizeBlocks(actual_int)
 
@@ -682,7 +703,7 @@ def test_neq():
         ]
     )
 
-    actual_bytes, _ = expr_bytes.__teal__(options)
+    actual_bytes, _ = expr_bytes.__teal__(teal2Options)
     actual_bytes.addIncoming()
     actual_bytes = TealBlock.NormalizeBlocks(actual_bytes)
 
@@ -702,7 +723,7 @@ def test_neq_overload():
         ]
     )
 
-    actual_int, _ = expr_int.__teal__(options)
+    actual_int, _ = expr_int.__teal__(teal2Options)
     actual_int.addIncoming()
     actual_int = TealBlock.NormalizeBlocks(actual_int)
 
@@ -720,7 +741,7 @@ def test_neq_overload():
         ]
     )
 
-    actual_bytes, _ = expr_bytes.__teal__(options)
+    actual_bytes, _ = expr_bytes.__teal__(teal2Options)
     actual_bytes.addIncoming()
     actual_bytes = TealBlock.NormalizeBlocks(actual_bytes)
 
@@ -744,7 +765,7 @@ def test_lt():
         [TealOp(args[0], Op.int, 2), TealOp(args[1], Op.int, 3), TealOp(expr, Op.lt)]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -760,7 +781,7 @@ def test_lt_overload():
         [TealOp(args[0], Op.int, 2), TealOp(args[1], Op.int, 3), TealOp(expr, Op.lt)]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -784,7 +805,7 @@ def test_le():
         [TealOp(args[0], Op.int, 1), TealOp(args[1], Op.int, 2), TealOp(expr, Op.le)]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -800,7 +821,7 @@ def test_le_overload():
         [TealOp(args[0], Op.int, 1), TealOp(args[1], Op.int, 2), TealOp(expr, Op.le)]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -824,7 +845,7 @@ def test_gt():
         [TealOp(args[0], Op.int, 2), TealOp(args[1], Op.int, 3), TealOp(expr, Op.gt)]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -840,7 +861,7 @@ def test_gt_overload():
         [TealOp(args[0], Op.int, 2), TealOp(args[1], Op.int, 3), TealOp(expr, Op.gt)]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -864,7 +885,7 @@ def test_ge():
         [TealOp(args[0], Op.int, 1), TealOp(args[1], Op.int, 10), TealOp(expr, Op.ge)]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -880,7 +901,7 @@ def test_ge_overload():
         [TealOp(args[0], Op.int, 1), TealOp(args[1], Op.int, 10), TealOp(expr, Op.ge)]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -908,12 +929,15 @@ def test_get_bit_int():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal3Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal2Options)
+
 
 def test_get_bit_bytes():
     args = [Bytes("base16", "0xFF"), Int(1)]
@@ -928,12 +952,15 @@ def test_get_bit_bytes():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal3Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal2Options)
+
 
 def test_get_bit_invalid():
     with pytest.raises(TealTypeError):
@@ -956,12 +983,15 @@ def test_get_byte():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal3Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal2Options)
+
 
 def test_get_byte_invalid():
     with pytest.raises(TealTypeError):
@@ -987,12 +1017,15 @@ def test_b_add():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_b_add_invalid():
     with pytest.raises(TealTypeError):
@@ -1018,12 +1051,15 @@ def test_b_minus():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_b_minus_invalid():
     with pytest.raises(TealTypeError):
@@ -1046,12 +1082,15 @@ def test_b_div():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_b_div_invalid():
     with pytest.raises(TealTypeError):
@@ -1074,12 +1113,15 @@ def test_b_mul():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_b_mul_invalid():
     with pytest.raises(TealTypeError):
@@ -1102,12 +1144,15 @@ def test_b_mod():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_b_mod_invalid():
     with pytest.raises(TealTypeError):
@@ -1130,12 +1175,15 @@ def test_b_and():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_b_and_invalid():
     with pytest.raises(TealTypeError):
@@ -1158,12 +1206,15 @@ def test_b_or():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_b_or_invalid():
     with pytest.raises(TealTypeError):
@@ -1186,12 +1237,15 @@ def test_b_xor():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_b_xor_invalid():
     with pytest.raises(TealTypeError):
@@ -1217,12 +1271,15 @@ def test_b_eq():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_b_eq_invalid():
     with pytest.raises(TealTypeError):
@@ -1248,12 +1305,15 @@ def test_b_neq():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_b_neq_invalid():
     with pytest.raises(TealTypeError):
@@ -1279,12 +1339,15 @@ def test_b_lt():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_b_lt_invalid():
     with pytest.raises(TealTypeError):
@@ -1310,12 +1373,15 @@ def test_b_le():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_b_le_invalid():
     with pytest.raises(TealTypeError):
@@ -1341,12 +1407,15 @@ def test_b_gt():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_b_gt_invalid():
     with pytest.raises(TealTypeError):
@@ -1372,12 +1441,15 @@ def test_b_ge():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal4Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal3Options)
+
 
 def test_b_ge_invalid():
     with pytest.raises(TealTypeError):
@@ -1385,3 +1457,43 @@ def test_b_ge_invalid():
 
     with pytest.raises(TealTypeError):
         BytesGe(Bytes("base16", "0xFF"), Int(2))
+
+
+def test_extract_uint():
+    for expression, op in (
+        (ExtractUint16, Op.extract_uint16),
+        (ExtractUint32, Op.extract_uint32),
+        (ExtractUint64, Op.extract_uint64),
+    ):
+        args = [
+            Bytes("base16", "0xFFFFFFFFFFFFFFFFFF"),
+            Int(2),
+        ]
+        expr = expression(args[0], args[1])
+        assert expr.type_of() == TealType.uint64
+
+        expected = TealSimpleBlock(
+            [
+                TealOp(args[0], Op.byte, "0xFFFFFFFFFFFFFFFFFF"),
+                TealOp(args[1], Op.int, 2),
+                TealOp(expr, op),
+            ]
+        )
+
+        actual, _ = expr.__teal__(teal5Options)
+        actual.addIncoming()
+        actual = TealBlock.NormalizeBlocks(actual)
+
+        assert actual == expected
+
+        with pytest.raises(TealInputError):
+            expr.__teal__(teal4Options)
+
+
+def test_extract_uint_invalid():
+    for expression in (ExtractUint16, ExtractUint32, ExtractUint64):
+        with pytest.raises(TealTypeError):
+            expression(Int(2), Txn.receiver())
+
+        with pytest.raises(TealTypeError):
+            expression(Bytes("base16", "0xFF"), Txn.receiver())
diff --git a/pyteal/ast/ternaryexpr_test.py b/pyteal/ast/ternaryexpr_test.py
index 1ba2335..adcf081 100644
--- a/pyteal/ast/ternaryexpr_test.py
+++ b/pyteal/ast/ternaryexpr_test.py
@@ -5,7 +5,10 @@ from .. import *
 # this is not necessary but mypy complains if it's not included
 from .. import CompileOptions
 
-options = CompileOptions()
+teal2Options = CompileOptions(version=2)
+teal3Options = CompileOptions(version=3)
+teal4Options = CompileOptions(version=4)
+teal5Options = CompileOptions(version=5)
 
 
 def test_ed25519verify():
@@ -22,7 +25,7 @@ def test_ed25519verify():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -54,7 +57,7 @@ def test_substring():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal2Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
@@ -72,6 +75,41 @@ def test_substring_invalid():
         Substring(Bytes("my string"), Int(0), Txn.sender())
 
 
+def test_extract():
+    args = [Bytes("my string"), Int(0), Int(2)]
+    expr = Extract(args[0], args[1], args[2])
+    assert expr.type_of() == TealType.bytes
+
+    expected = TealSimpleBlock(
+        [
+            TealOp(args[0], Op.byte, '"my string"'),
+            TealOp(args[1], Op.int, 0),
+            TealOp(args[2], Op.int, 2),
+            TealOp(expr, Op.extract3),
+        ]
+    )
+
+    actual, _ = expr.__teal__(teal5Options)
+    actual.addIncoming()
+    actual = TealBlock.NormalizeBlocks(actual)
+
+    assert actual == expected
+
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal4Options)
+
+
+def test_extract_invalid():
+    with pytest.raises(TealTypeError):
+        Extract(Int(0), Int(0), Int(2))
+
+    with pytest.raises(TealTypeError):
+        Extract(Bytes("my string"), Txn.sender(), Int(2))
+
+    with pytest.raises(TealTypeError):
+        Extract(Bytes("my string"), Int(0), Txn.sender())
+
+
 def test_set_bit_int():
     args = [Int(0), Int(2), Int(1)]
     expr = SetBit(args[0], args[1], args[2])
@@ -86,12 +124,15 @@ def test_set_bit_int():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal3Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal2Options)
+
 
 def test_set_bit_bytes():
     args = [Bytes("base16", "0x0000"), Int(0), Int(1)]
@@ -107,12 +148,15 @@ def test_set_bit_bytes():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal3Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal2Options)
+
 
 def test_set_bit_invalid():
     with pytest.raises(TealTypeError):
@@ -142,12 +186,15 @@ def test_set_byte():
         ]
     )
 
-    actual, _ = expr.__teal__(options)
+    actual, _ = expr.__teal__(teal3Options)
     actual.addIncoming()
     actual = TealBlock.NormalizeBlocks(actual)
 
     assert actual == expected
 
+    with pytest.raises(TealInputError):
+        expr.__teal__(teal2Options)
+
 
 def test_set_byte_invalid():
     with pytest.raises(TealTypeError):
diff --git a/pyteal/compiler/compiler_test.py b/pyteal/compiler/compiler_test.py
index e735885..a9a5697 100644
--- a/pyteal/compiler/compiler_test.py
+++ b/pyteal/compiler/compiler_test.py
@@ -816,7 +816,7 @@ app_global_put
 retsub
     """.strip()
     actual = compileTeal(program, Mode.Application, version=4, assembleConstants=False)
-    assert expected == actual
+    assert actual == expected
 
 
 def test_compile_subroutine_with_return():
@@ -869,7 +869,7 @@ app_global_get
 retsub
     """.strip()
     actual = compileTeal(program, Mode.Application, version=4, assembleConstants=False)
-    assert expected == actual
+    assert actual == expected
 
 
 def test_compile_subroutine_many_args():
@@ -916,7 +916,7 @@ load 5
 retsub
     """.strip()
     actual = compileTeal(program, Mode.Application, version=4, assembleConstants=False)
-    assert expected == actual
+    assert actual == expected
 
 
 def test_compile_subroutine_recursive():
@@ -967,7 +967,154 @@ sub0_l6:
 retsub
     """.strip()
     actual = compileTeal(program, Mode.Application, version=4, assembleConstants=False)
-    assert expected == actual
+    assert actual == expected
+
+
+def test_compile_subroutine_recursive_5():
+    @Subroutine(TealType.uint64)
+    def isEven(i: Expr) -> Expr:
+        return (
+            If(i == Int(0))
+            .Then(Int(1))
+            .ElseIf(i == Int(1))
+            .Then(Int(0))
+            .Else(isEven(i - Int(2)))
+        )
+
+    program = Return(isEven(Int(6)))
+
+    expected = """#pragma version 5
+int 6
+callsub sub0
+return
+sub0: // isEven
+store 0
+load 0
+int 0
+==
+bnz sub0_l5
+load 0
+int 1
+==
+bnz sub0_l4
+load 0
+int 2
+-
+load 0
+swap
+callsub sub0
+swap
+store 0
+sub0_l3:
+b sub0_l6
+sub0_l4:
+int 0
+b sub0_l3
+sub0_l5:
+int 1
+sub0_l6:
+retsub
+    """.strip()
+    actual = compileTeal(program, Mode.Application, version=5, assembleConstants=False)
+    assert actual == expected
+
+
+def test_compile_subroutine_recursive_multiple_args():
+    @Subroutine(TealType.uint64)
+    def multiplyByAdding(a, b):
+        return (
+            If(a == Int(0))
+            .Then(Return(Int(0)))
+            .Else(Return(b + multiplyByAdding(a - Int(1), b)))
+        )
+
+    program = Return(multiplyByAdding(Int(3), Int(5)))
+
+    expected = """#pragma version 4
+int 3
+int 5
+callsub sub0
+return
+sub0: // multiplyByAdding
+store 1
+store 0
+load 0
+int 0
+==
+bnz sub0_l2
+load 1
+load 0
+int 1
+-
+load 1
+load 0
+load 1
+dig 3
+dig 3
+callsub sub0
+store 0
+store 1
+load 0
+swap
+store 0
+swap
+pop
+swap
+pop
++
+retsub
+sub0_l2:
+int 0
+retsub
+    """.strip()
+    actual = compileTeal(program, Mode.Application, version=4, assembleConstants=False)
+    assert actual == expected
+
+
+def test_compile_subroutine_recursive_multiple_args_5():
+    @Subroutine(TealType.uint64)
+    def multiplyByAdding(a, b):
+        return (
+            If(a == Int(0))
+            .Then(Return(Int(0)))
+            .Else(Return(b + multiplyByAdding(a - Int(1), b)))
+        )
+
+    program = Return(multiplyByAdding(Int(3), Int(5)))
+
+    expected = """#pragma version 5
+int 3
+int 5
+callsub sub0
+return
+sub0: // multiplyByAdding
+store 1
+store 0
+load 0
+int 0
+==
+bnz sub0_l2
+load 1
+load 0
+int 1
+-
+load 1
+load 0
+load 1
+uncover 3
+uncover 3
+callsub sub0
+cover 2
+store 1
+store 0
++
+retsub
+sub0_l2:
+int 0
+retsub
+    """.strip()
+    actual = compileTeal(program, Mode.Application, version=5, assembleConstants=False)
+    assert actual == expected
 
 
 def test_compile_subroutine_mutually_recursive():
@@ -1031,7 +1178,67 @@ sub1_l3:
 retsub
     """.strip()
     actual = compileTeal(program, Mode.Application, version=4, assembleConstants=False)
-    assert expected == actual
+    assert actual == expected
+
+
+def test_compile_subroutine_mutually_recursive_5():
+    @Subroutine(TealType.uint64)
+    def isEven(i: Expr) -> Expr:
+        return If(i == Int(0), Int(1), Not(isOdd(i - Int(1))))
+
+    @Subroutine(TealType.uint64)
+    def isOdd(i: Expr) -> Expr:
+        return If(i == Int(0), Int(0), Not(isEven(i - Int(1))))
+
+    program = Return(isEven(Int(6)))
+
+    expected = """#pragma version 5
+int 6
+callsub sub0
+return
+sub0: // isEven
+store 0
+load 0
+int 0
+==
+bnz sub0_l2
+load 0
+int 1
+-
+load 0
+swap
+callsub sub1
+swap
+store 0
+!
+b sub0_l3
+sub0_l2:
+int 1
+sub0_l3:
+retsub
+sub1: // isOdd
+store 1
+load 1
+int 0
+==
+bnz sub1_l2
+load 1
+int 1
+-
+load 1
+swap
+callsub sub0
+swap
+store 1
+!
+b sub1_l3
+sub1_l2:
+int 0
+sub1_l3:
+retsub
+    """.strip()
+    actual = compileTeal(program, Mode.Application, version=5, assembleConstants=False)
+    assert actual == expected
 
 
 def test_compile_loop_in_subroutine():
@@ -1071,7 +1278,7 @@ sub0_l3:
 retsub
     """.strip()
     actual = compileTeal(program, Mode.Application, version=4, assembleConstants=False)
-    assert expected == actual
+    assert actual == expected
 
 
 def test_compile_subroutine_assemble_constants():
@@ -1129,4 +1336,4 @@ app_global_put
 retsub
     """.strip()
     actual = compileTeal(program, Mode.Application, version=4, assembleConstants=True)
-    assert expected == actual
+    assert actual == expected
diff --git a/pyteal/compiler/subroutines_test.py b/pyteal/compiler/subroutines_test.py
index 820e192..6ec26f7 100644
--- a/pyteal/compiler/subroutines_test.py
+++ b/pyteal/compiler/subroutines_test.py
@@ -138,42 +138,116 @@ def test_findRecursionPoints_direct_and_mutual_recursion():
 
 
 def test_spillLocalSlotsDuringRecursion_no_subroutines():
-    l1Label = LabelReference("l1")
-    mainOps = [
-        TealOp(None, Op.txn, "Fee"),
-        TealOp(None, Op.int, 0),
-        TealOp(None, Op.eq),
-        TealOp(None, Op.bz, l1Label),
-        TealOp(None, Op.int, 1),
-        TealOp(None, Op.return_),
-        TealLabel(None, l1Label),
-        TealOp(None, Op.int, 0),
-        TealOp(None, Op.return_),
-    ]
+    for version in (4, 5):
+        l1Label = LabelReference("l1")
+        mainOps = [
+            TealOp(None, Op.txn, "Fee"),
+            TealOp(None, Op.int, 0),
+            TealOp(None, Op.eq),
+            TealOp(None, Op.bz, l1Label),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.return_),
+            TealLabel(None, l1Label),
+            TealOp(None, Op.int, 0),
+            TealOp(None, Op.return_),
+        ]
 
-    subroutineMapping = {None: mainOps}
+        subroutineMapping = {None: mainOps}
 
-    subroutineGraph = dict()
+        subroutineGraph = dict()
 
-    localSlots = {None: set()}
+        localSlots = {None: set()}
 
-    spillLocalSlotsDuringRecursion(subroutineMapping, subroutineGraph, localSlots)
+        spillLocalSlotsDuringRecursion(
+            version, subroutineMapping, subroutineGraph, localSlots
+        )
 
-    assert mainOps == [
-        TealOp(None, Op.txn, "Fee"),
-        TealOp(None, Op.int, 0),
-        TealOp(None, Op.eq),
-        TealOp(None, Op.bz, l1Label),
-        TealOp(None, Op.int, 1),
-        TealOp(None, Op.return_),
-        TealLabel(None, l1Label),
-        TealOp(None, Op.int, 0),
-        TealOp(None, Op.return_),
-    ]
+        assert mainOps == [
+            TealOp(None, Op.txn, "Fee"),
+            TealOp(None, Op.int, 0),
+            TealOp(None, Op.eq),
+            TealOp(None, Op.bz, l1Label),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.return_),
+            TealLabel(None, l1Label),
+            TealOp(None, Op.int, 0),
+            TealOp(None, Op.return_),
+        ]
 
 
 def test_spillLocalSlotsDuringRecursion_1_subroutine_no_recursion():
-    subroutine = SubroutineDefinition(lambda: None, TealType.uint64)
+    for version in (4, 5):
+        subroutine = SubroutineDefinition(lambda: None, TealType.uint64)
+
+        subroutineL1Label = LabelReference("l1")
+        subroutineOps = [
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.load, 0),
+            TealOp(None, Op.int, 0),
+            TealOp(None, Op.eq),
+            TealOp(None, Op.bnz, subroutineL1Label),
+            TealOp(None, Op.err),
+            TealLabel(None, subroutineL1Label),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.retsub),
+        ]
+
+        l1Label = LabelReference("l1")
+        mainOps = [
+            TealOp(None, Op.txn, "Fee"),
+            TealOp(None, Op.int, 0),
+            TealOp(None, Op.eq),
+            TealOp(None, Op.bz, l1Label),
+            TealOp(None, Op.int, 100),
+            TealOp(None, Op.callsub, subroutine),
+            TealOp(None, Op.return_),
+            TealLabel(None, l1Label),
+            TealOp(None, Op.int, 0),
+            TealOp(None, Op.return_),
+        ]
+
+        subroutineMapping = {None: mainOps, subroutine: subroutineOps}
+
+        subroutineGraph = {subroutine: set()}
+
+        localSlots = {None: set(), subroutine: {0}}
+
+        spillLocalSlotsDuringRecursion(
+            version, subroutineMapping, subroutineGraph, localSlots
+        )
+
+        assert subroutineMapping == {
+            None: [
+                TealOp(None, Op.txn, "Fee"),
+                TealOp(None, Op.int, 0),
+                TealOp(None, Op.eq),
+                TealOp(None, Op.bz, l1Label),
+                TealOp(None, Op.int, 100),
+                TealOp(None, Op.callsub, subroutine),
+                TealOp(None, Op.return_),
+                TealLabel(None, l1Label),
+                TealOp(None, Op.int, 0),
+                TealOp(None, Op.return_),
+            ],
+            subroutine: [
+                TealOp(None, Op.store, 0),
+                TealOp(None, Op.load, 0),
+                TealOp(None, Op.int, 0),
+                TealOp(None, Op.eq),
+                TealOp(None, Op.bnz, subroutineL1Label),
+                TealOp(None, Op.err),
+                TealLabel(None, subroutineL1Label),
+                TealOp(None, Op.int, 1),
+                TealOp(None, Op.retsub),
+            ],
+        }
+
+
+def test_spillLocalSlotsDuringRecursion_1_subroutine_recursion_v4():
+    def sub1Impl(a1):
+        return None
+
+    subroutine = SubroutineDefinition(sub1Impl, TealType.uint64)
 
     subroutineL1Label = LabelReference("l1")
     subroutineOps = [
@@ -182,7 +256,13 @@ def test_spillLocalSlotsDuringRecursion_1_subroutine_no_recursion():
         TealOp(None, Op.int, 0),
         TealOp(None, Op.eq),
         TealOp(None, Op.bnz, subroutineL1Label),
-        TealOp(None, Op.err),
+        TealOp(None, Op.load, 0),
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.minus),
+        TealOp(None, Op.callsub, subroutine),
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.add),
+        TealOp(None, Op.retsub),
         TealLabel(None, subroutineL1Label),
         TealOp(None, Op.int, 1),
         TealOp(None, Op.retsub),
@@ -204,11 +284,11 @@ def test_spillLocalSlotsDuringRecursion_1_subroutine_no_recursion():
 
     subroutineMapping = {None: mainOps, subroutine: subroutineOps}
 
-    subroutineGraph = {subroutine: set()}
+    subroutineGraph = {subroutine: {subroutine}}
 
     localSlots = {None: set(), subroutine: {0}}
 
-    spillLocalSlotsDuringRecursion(subroutineMapping, subroutineGraph, localSlots)
+    spillLocalSlotsDuringRecursion(4, subroutineMapping, subroutineGraph, localSlots)
 
     assert subroutineMapping == {
         None: [
@@ -229,7 +309,19 @@ def test_spillLocalSlotsDuringRecursion_1_subroutine_no_recursion():
             TealOp(None, Op.int, 0),
             TealOp(None, Op.eq),
             TealOp(None, Op.bnz, subroutineL1Label),
-            TealOp(None, Op.err),
+            TealOp(None, Op.load, 0),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.minus),
+            TealOp(None, Op.load, 0),
+            TealOp(None, Op.dig, 1),
+            TealOp(None, Op.callsub, subroutine),
+            TealOp(None, Op.swap),
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.swap),
+            TealOp(None, Op.pop),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.add),
+            TealOp(None, Op.retsub),
             TealLabel(None, subroutineL1Label),
             TealOp(None, Op.int, 1),
             TealOp(None, Op.retsub),
@@ -237,7 +329,7 @@ def test_spillLocalSlotsDuringRecursion_1_subroutine_no_recursion():
     }
 
 
-def test_spillLocalSlotsDuringRecursion_1_subroutine_recursion():
+def test_spillLocalSlotsDuringRecursion_1_subroutine_recursion_v5():
     def sub1Impl(a1):
         return None
 
@@ -282,7 +374,7 @@ def test_spillLocalSlotsDuringRecursion_1_subroutine_recursion():
 
     localSlots = {None: set(), subroutine: {0}}
 
-    spillLocalSlotsDuringRecursion(subroutineMapping, subroutineGraph, localSlots)
+    spillLocalSlotsDuringRecursion(5, subroutineMapping, subroutineGraph, localSlots)
 
     assert subroutineMapping == {
         None: [
@@ -307,12 +399,10 @@ def test_spillLocalSlotsDuringRecursion_1_subroutine_recursion():
             TealOp(None, Op.int, 1),
             TealOp(None, Op.minus),
             TealOp(None, Op.load, 0),
-            TealOp(None, Op.dig, 1),
+            TealOp(None, Op.swap),
             TealOp(None, Op.callsub, subroutine),
             TealOp(None, Op.swap),
             TealOp(None, Op.store, 0),
-            TealOp(None, Op.swap),
-            TealOp(None, Op.pop),
             TealOp(None, Op.int, 1),
             TealOp(None, Op.add),
             TealOp(None, Op.retsub),
@@ -324,6 +414,130 @@ def test_spillLocalSlotsDuringRecursion_1_subroutine_recursion():
 
 
 def test_spillLocalSlotsDuringRecursion_multiple_subroutines_no_recursion():
+    for version in (4, 5):
+
+        def sub1Impl(a1):
+            return None
+
+        def sub2Impl(a1, a2):
+            return None
+
+        def sub3Impl(a1, a2, a3):
+            return None
+
+        subroutine1 = SubroutineDefinition(sub1Impl, TealType.uint64)
+        subroutine2 = SubroutineDefinition(sub1Impl, TealType.uint64)
+        subroutine3 = SubroutineDefinition(sub1Impl, TealType.none)
+
+        subroutine1L1Label = LabelReference("l1")
+        subroutine1Ops = [
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.load, 0),
+            TealOp(None, Op.int, 0),
+            TealOp(None, Op.eq),
+            TealOp(None, Op.bnz, subroutine1L1Label),
+            TealOp(None, Op.err),
+            TealLabel(None, subroutine1L1Label),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.callsub, subroutine3),
+            TealOp(None, Op.retsub),
+        ]
+
+        subroutine2L1Label = LabelReference("l1")
+        subroutine2Ops = [
+            TealOp(None, Op.store, 1),
+            TealOp(None, Op.load, 1),
+            TealOp(None, Op.int, 0),
+            TealOp(None, Op.eq),
+            TealOp(None, Op.bnz, subroutine2L1Label),
+            TealOp(None, Op.err),
+            TealLabel(None, subroutine2L1Label),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.retsub),
+        ]
+
+        subroutine3Ops = [
+            TealOp(None, Op.retsub),
+        ]
+
+        l1Label = LabelReference("l1")
+        mainOps = [
+            TealOp(None, Op.txn, "Fee"),
+            TealOp(None, Op.int, 0),
+            TealOp(None, Op.eq),
+            TealOp(None, Op.bz, l1Label),
+            TealOp(None, Op.int, 100),
+            TealOp(None, Op.callsub, subroutine1),
+            TealOp(None, Op.return_),
+            TealLabel(None, l1Label),
+            TealOp(None, Op.int, 101),
+            TealOp(None, Op.callsub, subroutine2),
+            TealOp(None, Op.return_),
+        ]
+
+        subroutineMapping = {
+            None: mainOps,
+            subroutine1: subroutine1Ops,
+            subroutine2: subroutine2Ops,
+            subroutine3: subroutine3Ops,
+        }
+
+        subroutineGraph = {
+            subroutine1: {subroutine2},
+            subroutine2: set(),
+            subroutine3: set(),
+        }
+
+        localSlots = {None: set(), subroutine1: {0}, subroutine2: {1}, subroutine3: {}}
+
+        spillLocalSlotsDuringRecursion(
+            version, subroutineMapping, subroutineGraph, localSlots
+        )
+
+        assert subroutineMapping == {
+            None: [
+                TealOp(None, Op.txn, "Fee"),
+                TealOp(None, Op.int, 0),
+                TealOp(None, Op.eq),
+                TealOp(None, Op.bz, l1Label),
+                TealOp(None, Op.int, 100),
+                TealOp(None, Op.callsub, subroutine1),
+                TealOp(None, Op.return_),
+                TealLabel(None, l1Label),
+                TealOp(None, Op.int, 101),
+                TealOp(None, Op.callsub, subroutine2),
+                TealOp(None, Op.return_),
+            ],
+            subroutine1: [
+                TealOp(None, Op.store, 0),
+                TealOp(None, Op.load, 0),
+                TealOp(None, Op.int, 0),
+                TealOp(None, Op.eq),
+                TealOp(None, Op.bnz, subroutine1L1Label),
+                TealOp(None, Op.err),
+                TealLabel(None, subroutine1L1Label),
+                TealOp(None, Op.int, 1),
+                TealOp(None, Op.callsub, subroutine3),
+                TealOp(None, Op.retsub),
+            ],
+            subroutine2: [
+                TealOp(None, Op.store, 1),
+                TealOp(None, Op.load, 1),
+                TealOp(None, Op.int, 0),
+                TealOp(None, Op.eq),
+                TealOp(None, Op.bnz, subroutine2L1Label),
+                TealOp(None, Op.err),
+                TealLabel(None, subroutine2L1Label),
+                TealOp(None, Op.int, 1),
+                TealOp(None, Op.retsub),
+            ],
+            subroutine3: [
+                TealOp(None, Op.retsub),
+            ],
+        }
+
+
+def test_spillLocalSlotsDuringRecursion_multiple_subroutines_recursion_v4():
     def sub1Impl(a1):
         return None
 
@@ -344,10 +558,15 @@ def test_spillLocalSlotsDuringRecursion_multiple_subroutines_no_recursion():
         TealOp(None, Op.int, 0),
         TealOp(None, Op.eq),
         TealOp(None, Op.bnz, subroutine1L1Label),
-        TealOp(None, Op.err),
-        TealLabel(None, subroutine1L1Label),
+        TealOp(None, Op.load, 0),
         TealOp(None, Op.int, 1),
-        TealOp(None, Op.callsub, subroutine3),
+        TealOp(None, Op.minus),
+        TealOp(None, Op.callsub, subroutine1),
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.add),
+        TealOp(None, Op.retsub),
+        TealLabel(None, subroutine1L1Label),
+        TealOp(None, Op.load, 255),
         TealOp(None, Op.retsub),
     ]
 
@@ -358,18 +577,27 @@ def test_spillLocalSlotsDuringRecursion_multiple_subroutines_no_recursion():
         TealOp(None, Op.int, 0),
         TealOp(None, Op.eq),
         TealOp(None, Op.bnz, subroutine2L1Label),
-        TealOp(None, Op.err),
+        TealOp(None, Op.load, 0),
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.minus),
+        TealOp(None, Op.callsub, subroutine1),
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.add),
+        TealOp(None, Op.retsub),
         TealLabel(None, subroutine2L1Label),
         TealOp(None, Op.int, 1),
         TealOp(None, Op.retsub),
     ]
 
     subroutine3Ops = [
+        TealOp(None, Op.callsub, subroutine3),
         TealOp(None, Op.retsub),
     ]
 
     l1Label = LabelReference("l1")
     mainOps = [
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.store, 255),
         TealOp(None, Op.txn, "Fee"),
         TealOp(None, Op.int, 0),
         TealOp(None, Op.eq),
@@ -381,6 +609,7 @@ def test_spillLocalSlotsDuringRecursion_multiple_subroutines_no_recursion():
         TealOp(None, Op.int, 101),
         TealOp(None, Op.callsub, subroutine2),
         TealOp(None, Op.return_),
+        TealOp(None, Op.callsub, subroutine3),
     ]
 
     subroutineMapping = {
@@ -391,17 +620,19 @@ def test_spillLocalSlotsDuringRecursion_multiple_subroutines_no_recursion():
     }
 
     subroutineGraph = {
-        subroutine1: {subroutine2},
-        subroutine2: set(),
-        subroutine3: set(),
+        subroutine1: {subroutine1},
+        subroutine2: {subroutine1},
+        subroutine3: {subroutine3},
     }
 
     localSlots = {None: set(), subroutine1: {0}, subroutine2: {1}, subroutine3: {}}
 
-    spillLocalSlotsDuringRecursion(subroutineMapping, subroutineGraph, localSlots)
+    spillLocalSlotsDuringRecursion(4, subroutineMapping, subroutineGraph, localSlots)
 
     assert subroutineMapping == {
         None: [
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.store, 255),
             TealOp(None, Op.txn, "Fee"),
             TealOp(None, Op.int, 0),
             TealOp(None, Op.eq),
@@ -413,6 +644,7 @@ def test_spillLocalSlotsDuringRecursion_multiple_subroutines_no_recursion():
             TealOp(None, Op.int, 101),
             TealOp(None, Op.callsub, subroutine2),
             TealOp(None, Op.return_),
+            TealOp(None, Op.callsub, subroutine3),
         ],
         subroutine1: [
             TealOp(None, Op.store, 0),
@@ -420,10 +652,21 @@ def test_spillLocalSlotsDuringRecursion_multiple_subroutines_no_recursion():
             TealOp(None, Op.int, 0),
             TealOp(None, Op.eq),
             TealOp(None, Op.bnz, subroutine1L1Label),
-            TealOp(None, Op.err),
-            TealLabel(None, subroutine1L1Label),
+            TealOp(None, Op.load, 0),
             TealOp(None, Op.int, 1),
-            TealOp(None, Op.callsub, subroutine3),
+            TealOp(None, Op.minus),
+            TealOp(None, Op.load, 0),
+            TealOp(None, Op.dig, 1),
+            TealOp(None, Op.callsub, subroutine1),
+            TealOp(None, Op.swap),
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.swap),
+            TealOp(None, Op.pop),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.add),
+            TealOp(None, Op.retsub),
+            TealLabel(None, subroutine1L1Label),
+            TealOp(None, Op.load, 255),
             TealOp(None, Op.retsub),
         ],
         subroutine2: [
@@ -432,18 +675,25 @@ def test_spillLocalSlotsDuringRecursion_multiple_subroutines_no_recursion():
             TealOp(None, Op.int, 0),
             TealOp(None, Op.eq),
             TealOp(None, Op.bnz, subroutine2L1Label),
-            TealOp(None, Op.err),
+            TealOp(None, Op.load, 0),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.minus),
+            TealOp(None, Op.callsub, subroutine1),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.add),
+            TealOp(None, Op.retsub),
             TealLabel(None, subroutine2L1Label),
             TealOp(None, Op.int, 1),
             TealOp(None, Op.retsub),
         ],
         subroutine3: [
+            TealOp(None, Op.callsub, subroutine3),
             TealOp(None, Op.retsub),
         ],
     }
 
 
-def test_spillLocalSlotsDuringRecursion_multiple_subroutines_recursion():
+def test_spillLocalSlotsDuringRecursion_multiple_subroutines_recursion_v5():
     def sub1Impl(a1):
         return None
 
@@ -533,7 +783,7 @@ def test_spillLocalSlotsDuringRecursion_multiple_subroutines_recursion():
 
     localSlots = {None: set(), subroutine1: {0}, subroutine2: {1}, subroutine3: {}}
 
-    spillLocalSlotsDuringRecursion(subroutineMapping, subroutineGraph, localSlots)
+    spillLocalSlotsDuringRecursion(5, subroutineMapping, subroutineGraph, localSlots)
 
     assert subroutineMapping == {
         None: [
@@ -562,12 +812,10 @@ def test_spillLocalSlotsDuringRecursion_multiple_subroutines_recursion():
             TealOp(None, Op.int, 1),
             TealOp(None, Op.minus),
             TealOp(None, Op.load, 0),
-            TealOp(None, Op.dig, 1),
+            TealOp(None, Op.swap),
             TealOp(None, Op.callsub, subroutine1),
             TealOp(None, Op.swap),
             TealOp(None, Op.store, 0),
-            TealOp(None, Op.swap),
-            TealOp(None, Op.pop),
             TealOp(None, Op.int, 1),
             TealOp(None, Op.add),
             TealOp(None, Op.retsub),
@@ -599,6 +847,436 @@ def test_spillLocalSlotsDuringRecursion_multiple_subroutines_recursion():
     }
 
 
+def test_spillLocalSlotsDuringRecursion_recursive_many_args_no_return_v4():
+    def subImpl(a1, a2, a3):
+        return None
+
+    subroutine = SubroutineDefinition(subImpl, TealType.none)
+
+    subroutineOps = [
+        TealOp(None, Op.store, 0),
+        TealOp(None, Op.store, 1),
+        TealOp(None, Op.store, 2),
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.int, 2),
+        TealOp(None, Op.int, 3),
+        TealOp(None, Op.callsub, subroutine),
+        TealOp(None, Op.retsub),
+    ]
+
+    mainOps = [
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.int, 2),
+        TealOp(None, Op.int, 3),
+        TealOp(None, Op.callsub, subroutine),
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.return_),
+    ]
+
+    subroutineMapping = {
+        None: mainOps,
+        subroutine: subroutineOps,
+    }
+
+    subroutineGraph = {
+        subroutine: {subroutine},
+    }
+
+    localSlots = {None: set(), subroutine: {0, 1, 2}}
+
+    spillLocalSlotsDuringRecursion(4, subroutineMapping, subroutineGraph, localSlots)
+
+    assert subroutineMapping == {
+        None: [
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.int, 2),
+            TealOp(None, Op.int, 3),
+            TealOp(None, Op.callsub, subroutine),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.return_),
+        ],
+        subroutine: [
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.store, 1),
+            TealOp(None, Op.store, 2),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.int, 2),
+            TealOp(None, Op.int, 3),
+            TealOp(None, Op.load, 0),
+            TealOp(None, Op.load, 1),
+            TealOp(None, Op.load, 2),
+            TealOp(None, Op.dig, 5),
+            TealOp(None, Op.dig, 5),
+            TealOp(None, Op.dig, 5),
+            TealOp(None, Op.callsub, subroutine),
+            TealOp(None, Op.store, 2),
+            TealOp(None, Op.store, 1),
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.pop),
+            TealOp(None, Op.pop),
+            TealOp(None, Op.pop),
+            TealOp(None, Op.retsub),
+        ],
+    }
+
+
+def test_spillLocalSlotsDuringRecursion_recursive_many_args_no_return_v5():
+    def subImpl(a1, a2, a3):
+        return None
+
+    subroutine = SubroutineDefinition(subImpl, TealType.none)
+
+    subroutineOps = [
+        TealOp(None, Op.store, 0),
+        TealOp(None, Op.store, 1),
+        TealOp(None, Op.store, 2),
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.int, 2),
+        TealOp(None, Op.int, 3),
+        TealOp(None, Op.callsub, subroutine),
+        TealOp(None, Op.retsub),
+    ]
+
+    mainOps = [
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.int, 2),
+        TealOp(None, Op.int, 3),
+        TealOp(None, Op.callsub, subroutine),
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.return_),
+    ]
+
+    subroutineMapping = {
+        None: mainOps,
+        subroutine: subroutineOps,
+    }
+
+    subroutineGraph = {
+        subroutine: {subroutine},
+    }
+
+    localSlots = {None: set(), subroutine: {0, 1, 2}}
+
+    spillLocalSlotsDuringRecursion(5, subroutineMapping, subroutineGraph, localSlots)
+
+    assert subroutineMapping == {
+        None: [
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.int, 2),
+            TealOp(None, Op.int, 3),
+            TealOp(None, Op.callsub, subroutine),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.return_),
+        ],
+        subroutine: [
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.store, 1),
+            TealOp(None, Op.store, 2),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.int, 2),
+            TealOp(None, Op.int, 3),
+            TealOp(None, Op.load, 0),
+            TealOp(None, Op.load, 1),
+            TealOp(None, Op.load, 2),
+            TealOp(None, Op.uncover, 5),
+            TealOp(None, Op.uncover, 5),
+            TealOp(None, Op.uncover, 5),
+            TealOp(None, Op.callsub, subroutine),
+            TealOp(None, Op.store, 2),
+            TealOp(None, Op.store, 1),
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.retsub),
+        ],
+    }
+
+
+def test_spillLocalSlotsDuringRecursion_recursive_many_args_return_v4():
+    def subImpl(a1, a2, a3):
+        return None
+
+    subroutine = SubroutineDefinition(subImpl, TealType.uint64)
+
+    subroutineOps = [
+        TealOp(None, Op.store, 0),
+        TealOp(None, Op.store, 1),
+        TealOp(None, Op.store, 2),
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.int, 2),
+        TealOp(None, Op.int, 3),
+        TealOp(None, Op.callsub, subroutine),
+        TealOp(None, Op.retsub),
+    ]
+
+    mainOps = [
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.int, 2),
+        TealOp(None, Op.int, 3),
+        TealOp(None, Op.callsub, subroutine),
+        TealOp(None, Op.return_),
+    ]
+
+    subroutineMapping = {
+        None: mainOps,
+        subroutine: subroutineOps,
+    }
+
+    subroutineGraph = {
+        subroutine: {subroutine},
+    }
+
+    localSlots = {None: set(), subroutine: {0, 1, 2}}
+
+    spillLocalSlotsDuringRecursion(4, subroutineMapping, subroutineGraph, localSlots)
+
+    assert subroutineMapping == {
+        None: [
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.int, 2),
+            TealOp(None, Op.int, 3),
+            TealOp(None, Op.callsub, subroutine),
+            TealOp(None, Op.return_),
+        ],
+        subroutine: [
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.store, 1),
+            TealOp(None, Op.store, 2),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.int, 2),
+            TealOp(None, Op.int, 3),
+            TealOp(None, Op.load, 0),
+            TealOp(None, Op.load, 1),
+            TealOp(None, Op.load, 2),
+            TealOp(None, Op.dig, 5),
+            TealOp(None, Op.dig, 5),
+            TealOp(None, Op.dig, 5),
+            TealOp(None, Op.callsub, subroutine),
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.store, 2),
+            TealOp(None, Op.store, 1),
+            TealOp(None, Op.load, 0),
+            TealOp(None, Op.swap),
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.swap),
+            TealOp(None, Op.pop),
+            TealOp(None, Op.swap),
+            TealOp(None, Op.pop),
+            TealOp(None, Op.swap),
+            TealOp(None, Op.pop),
+            TealOp(None, Op.retsub),
+        ],
+    }
+
+
+def test_spillLocalSlotsDuringRecursion_recursive_many_args_return_v5():
+    def subImpl(a1, a2, a3):
+        return None
+
+    subroutine = SubroutineDefinition(subImpl, TealType.uint64)
+
+    subroutineOps = [
+        TealOp(None, Op.store, 0),
+        TealOp(None, Op.store, 1),
+        TealOp(None, Op.store, 2),
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.int, 2),
+        TealOp(None, Op.int, 3),
+        TealOp(None, Op.callsub, subroutine),
+        TealOp(None, Op.retsub),
+    ]
+
+    mainOps = [
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.int, 2),
+        TealOp(None, Op.int, 3),
+        TealOp(None, Op.callsub, subroutine),
+        TealOp(None, Op.return_),
+    ]
+
+    subroutineMapping = {
+        None: mainOps,
+        subroutine: subroutineOps,
+    }
+
+    subroutineGraph = {
+        subroutine: {subroutine},
+    }
+
+    localSlots = {None: set(), subroutine: {0, 1, 2}}
+
+    spillLocalSlotsDuringRecursion(5, subroutineMapping, subroutineGraph, localSlots)
+
+    assert subroutineMapping == {
+        None: [
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.int, 2),
+            TealOp(None, Op.int, 3),
+            TealOp(None, Op.callsub, subroutine),
+            TealOp(None, Op.return_),
+        ],
+        subroutine: [
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.store, 1),
+            TealOp(None, Op.store, 2),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.int, 2),
+            TealOp(None, Op.int, 3),
+            TealOp(None, Op.load, 0),
+            TealOp(None, Op.load, 1),
+            TealOp(None, Op.load, 2),
+            TealOp(None, Op.uncover, 5),
+            TealOp(None, Op.uncover, 5),
+            TealOp(None, Op.uncover, 5),
+            TealOp(None, Op.callsub, subroutine),
+            TealOp(None, Op.cover, 3),
+            TealOp(None, Op.store, 2),
+            TealOp(None, Op.store, 1),
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.retsub),
+        ],
+    }
+
+
+def test_spillLocalSlotsDuringRecursion_recursive_more_args_than_slots_v5():
+    def subImpl(a1, a2, a3):
+        return None
+
+    subroutine = SubroutineDefinition(subImpl, TealType.uint64)
+
+    subroutineOps = [
+        TealOp(None, Op.store, 0),
+        TealOp(None, Op.store, 1),
+        TealOp(None, Op.pop),
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.int, 2),
+        TealOp(None, Op.int, 3),
+        TealOp(None, Op.callsub, subroutine),
+        TealOp(None, Op.retsub),
+    ]
+
+    mainOps = [
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.int, 2),
+        TealOp(None, Op.int, 3),
+        TealOp(None, Op.callsub, subroutine),
+        TealOp(None, Op.return_),
+    ]
+
+    subroutineMapping = {
+        None: mainOps,
+        subroutine: subroutineOps,
+    }
+
+    subroutineGraph = {
+        subroutine: {subroutine},
+    }
+
+    localSlots = {None: set(), subroutine: {0, 1}}
+
+    spillLocalSlotsDuringRecursion(5, subroutineMapping, subroutineGraph, localSlots)
+
+    assert subroutineMapping == {
+        None: [
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.int, 2),
+            TealOp(None, Op.int, 3),
+            TealOp(None, Op.callsub, subroutine),
+            TealOp(None, Op.return_),
+        ],
+        subroutine: [
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.store, 1),
+            TealOp(None, Op.pop),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.int, 2),
+            TealOp(None, Op.int, 3),
+            TealOp(None, Op.load, 0),
+            TealOp(None, Op.cover, 3),
+            TealOp(None, Op.load, 1),
+            TealOp(None, Op.cover, 3),
+            TealOp(None, Op.callsub, subroutine),
+            TealOp(None, Op.cover, 2),
+            TealOp(None, Op.store, 1),
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.retsub),
+        ],
+    }
+
+
+def test_spillLocalSlotsDuringRecursion_recursive_more_slots_than_args_v5():
+    def subImpl(a1, a2, a3):
+        return None
+
+    subroutine = SubroutineDefinition(subImpl, TealType.uint64)
+
+    subroutineOps = [
+        TealOp(None, Op.store, 0),
+        TealOp(None, Op.store, 1),
+        TealOp(None, Op.store, 2),
+        TealOp(None, Op.int, 10),
+        TealOp(None, Op.store, 3),
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.int, 2),
+        TealOp(None, Op.int, 3),
+        TealOp(None, Op.callsub, subroutine),
+        TealOp(None, Op.retsub),
+    ]
+
+    mainOps = [
+        TealOp(None, Op.int, 1),
+        TealOp(None, Op.int, 2),
+        TealOp(None, Op.int, 3),
+        TealOp(None, Op.callsub, subroutine),
+        TealOp(None, Op.return_),
+    ]
+
+    subroutineMapping = {
+        None: mainOps,
+        subroutine: subroutineOps,
+    }
+
+    subroutineGraph = {
+        subroutine: {subroutine},
+    }
+
+    localSlots = {None: set(), subroutine: {0, 1, 2, 3}}
+
+    spillLocalSlotsDuringRecursion(5, subroutineMapping, subroutineGraph, localSlots)
+
+    assert subroutineMapping == {
+        None: [
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.int, 2),
+            TealOp(None, Op.int, 3),
+            TealOp(None, Op.callsub, subroutine),
+            TealOp(None, Op.return_),
+        ],
+        subroutine: [
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.store, 1),
+            TealOp(None, Op.store, 2),
+            TealOp(None, Op.int, 10),
+            TealOp(None, Op.store, 3),
+            TealOp(None, Op.int, 1),
+            TealOp(None, Op.int, 2),
+            TealOp(None, Op.int, 3),
+            TealOp(None, Op.load, 0),
+            TealOp(None, Op.load, 1),
+            TealOp(None, Op.load, 2),
+            TealOp(None, Op.load, 3),
+            TealOp(None, Op.uncover, 6),
+            TealOp(None, Op.uncover, 6),
+            TealOp(None, Op.uncover, 6),
+            TealOp(None, Op.callsub, subroutine),
+            TealOp(None, Op.cover, 4),
+            TealOp(None, Op.store, 3),
+            TealOp(None, Op.store, 2),
+            TealOp(None, Op.store, 1),
+            TealOp(None, Op.store, 0),
+            TealOp(None, Op.retsub),
+        ],
+    }
+
+
 def test_resolveSubroutines():
     def sub1Impl(a1):
         return None