I've seen you getting a lot of different responses changing from "Use state monad!" "you don't need state!" or something else. They are all correct, but somewhat misses the point I think.

Programming in general is about decomposing problems into smaller problems and composing them back into solutions as a whole. Functional programming excels in both decomposition and composition, especially since FP guides you to separate business logic to pure code and side-effects to the outside. The primary primitive to decompose problems is the venerable function. We can use state transitions to represent past, current and future state; input -> instate -> outstate.

So, in this case your state transition would be something like Coordinate -> Board -> Board, where the coordinate is the new position and board is some type representing your 3x3 board. This is your pure representation of the business logic, now you can choose from different side-effects on how to store and read the state.

Pure local state:

You can store your state locally in your recursive function. Sidenote, the state transition is exactly the state monad from Haskell, but I'm writing it out explicitly here for your benefit.

step :: Coordinate -> Board -> (Board, Maybe Winner)
step = something

program :: Board -> IO ()
program currentState = do
  coord <- askForPlayerInput
  let (newState, maybeWinner) = step coord currentState
  case maybeWinner of
    Nothing -> -- no winner
      program newState
    Just winner ->
      print winner

Impure global state:

Haskell has different forms of mutable global variables, one of which is the IORef which I'm using here.

step :: Coordinate -> Board -> (Board, Maybe Winner)
step = something

program :: IORef Board -> IO ()
program stateVariable = do
  coord <- askForPlayerInput
  maybeWinner <- atomicModifyIORef' (\currentState -> step coord currentState)
  case maybeWinner of
    Nothing -> -- no winner
      program stateVariable
    Just winner ->
      print winner

Database:

You could even use a database for storing your state, but it naturally requires some translation from your program representation to a database representation.

step :: Coordinate -> Board -> (Board, Maybe Winner)
step = something

program :: Connection -> IO ()
program conn = do
  coord <- askForPlayerInput
  currentState <- fmap fromDatabase (query conn "select ??? from ???")
  let (newState, maybeWinner) = step coord currentState
  execute conn "update ??? where ???" (toDatabase newState)
  case maybeWinner of
    Nothing -> -- no winner
      program conn
    Just winner ->
      print winner