Is it possible to use recursion in onchain code?

Question

I originally asked Working with BuiltinByteString

One of the suggested solutions defined a recursive function in the on chain code. This did not work however and I've since been trying to determine if onchain code can contain any recursive function. I've tried to define the simplest validator function that uses recursion but the Plutus compiler always errors on:

GHC Core to PLC plugin: E042:Error: Unsupported feature: Use of Haskell Integer equality, possibly via the Haskell Eq typeclass

Here is my simple example:

{-# INLINABLE mkPolicy #-}
mkPolicy :: TxOutRef -> () -> ScriptContext -> Bool
mkPolicy oref () ctx = (fact 2) == (2 :: Integer)
  where
    fact :: Integer -> Integer
    fact 1 = 1
    fact n = multiplyInteger n  (fact (subtractInteger n 1))

I used this code as a template, and just replaced the mkPolicy function: https://github.com/input-output-hk/plutus-pioneer-program/blob/main/code/week05/src/Week05/NFT.hs

This is the first few lines of the error I get:

GHC Core to PLC plugin: E042:Error: Unsupported feature: Use of Haskell Integer equality, possibly via the Haskell Eq typeclass
Context: Compiling expr: GHC.Integer.Type.eqInteger#
Context: Compiling expr: GHC.Integer.Type.eqInteger# ds_d1hoe
Context: Compiling expr: GHC.Integer.Type.eqInteger# ds_d1hoe 1
Context: Compiling expr: case GHC.Integer.Type.eqInteger# ds_d1hoe 1
                         of wild [Occ=Once]
                         { __DEFAULT ->
                         GHC.Prim.tagToEnum# @ GHC.Types.Bool wild
                         }
Context: Compiling expr: case case GHC.Integer.Type.eqInteger# ds_d1hoe 1
                              of wild [Occ=Once]
                              { __DEFAULT ->
                              GHC.Prim.tagToEnum# @ GHC.Types.Bool wild
                              }
                         of {
                           GHC.Types.False ->
                             PlutusTx.Builtins.Internal.multiplyInteger
                               ds_d1hoe
                               (fact (PlutusTx.Builtins.Internal.subtractInteger ds_d1hoe 1));
                           GHC.Types.True -> 1
                         }
Context: Compiling expr: \ (ds_d1hoe :: GHC.Integer.Type.Integer) ->
                           case case GHC.Integer.Type.eqInteger# ds_d1hoe 1 of wild [Occ=Once]
                                { __DEFAULT ->
                                GHC.Prim.tagToEnum# @ GHC.Types.Bool wild
                                }
                           of {
                             GHC.Types.False ->
                               PlutusTx.Builtins.Internal.multiplyInteger
                                 ds_d1hoe
                                 (fact (PlutusTx.Builtins.Internal.subtractInteger ds_d1hoe 1));
                             GHC.Types.True -> 1
                           }

Answer 1

I was able to get something that works, but I couldn't explain why. It has to do with the way Template Haskell is generated:

{-# INLINABLE mkPolicy #-}
mkPolicy :: TxOutRef -> () -> ScriptContext -> Bool
mkPolicy oref () ctx = fact 2 == (2 :: Integer)
  where

    fact :: Integer -> Integer
    fact n 
      | n == 1 = 1
      | otherwise = n * fact (n - 1)

As you see, the problem is not recursion. Perhaps you should open an issue on the Plutus issue tracker and discuss with the people there whether this is a bug or a feature.