Is `Pair` a valid instance of `MonadRec`?

Question

In the paper Stack Safety for Free, Phil Freeman defines the MonadRec type class as follows.

class (Monad m) <= MonadRec m where
  tailRecM :: forall a b. (a -> m (Either a b)) -> a -> m b

An instance of the MonadRec class must satisfy the following laws.

1. tailRecM f a must be equivalent to f a >>= go where go (Left a) = f a >>= go and go (Right b) = pure b.
2. The stack usage of tailRecM f must be at most a constant multiple of the stack usage of f itself.

Now, consider the following Pair class in TypeScript.

class Pair<out A> {
  public constructor(
    public readonly fst: A,
    public readonly snd: A,
  ) {}

  public chain<A, B>(this: Pair<A>, arrow: (value: A) => Pair<B>): Pair<B> {
    return new Pair(arrow(this.fst).fst, arrow(this.snd).snd);
  }

  public static of<A>(value: A): Pair<A> {
    return new Pair(value, value);
  }
}

As you can see, Pair is a valid monad. Now, I want to define the chainRec function for Pair, which is the Fantasy Land equivalent of the tailRecM function defined by Phil Freeman. For simplicity, I first define my own Either type.

class Left<out A> {
  public readonly isLeft = true;

  public constructor(public readonly value: A) {}
}

class Right<out B> {
  public readonly isLeft = false;

  public constructor(public readonly value: B) {}
}

type Either<A, B> = Left<A> | Right<B>;

And then, I defined the chainRec function as follows inside the Pair class.

public static chainRec<A, B>(
  arrow: (value: A) => Pair<Either<A, B>>,
  value: A,
): Pair<B> {
  const rec = (either: Either<A, B>): Pair<B> => {
    const stack: Either<B, Either<A, B>>[] = [];

    let cursor: Either<Either<A, B>, Pair<B>> = new Left(either);

    while (stack.length > 0 || cursor.isLeft) {
      if (cursor.isLeft) {
        const either: Either<A, B> = cursor.value;
        if (either.isLeft) {
          const pair = arrow(either.value);
          cursor = new Left(pair.fst);
          stack.push(new Right(pair.snd));
        } else cursor = new Right(Pair.of(either.value));
      } else {
        const pair: Pair<B> = cursor.value;
        const frame = stack.pop()!;
        if (frame.isLeft) cursor = new Right(new Pair(frame.value, pair.snd));
        else {
          cursor = new Left(frame.value);
          stack.push(new Left(pair.fst));
        }
      }
    }

    return cursor.value;
  };

  return arrow(value).chain(rec);
}

Playground Link

It's easy to prove that this implementation of chainRec satisfies the first law. Pair.chainRec(f, a) is equivalent to

f(a).chain(function go(either) {
  return either.isLeft ? f(either.value).chain(go) : Pair.of(either.value);
});

However, I'm not sure whether it satisfies the second law.

• The stack usage of Pair.chainRec(f, a) must be at most a constant multiple of the stack usage of f itself.

I'm unsure because the rec function has a local stack variable which can grow arbitrarily large. Granted, the stack lives on the heap and only a reference to the stack lives on the stack. So, in that sense it does satisfy the second law. However, if we allow the chainRec function to use an arbitrarily large local stack then wouldn't we be able to create a valid instance of MonadRec for every possible monad? If the answer is no, then what are some example types that are valid instances of Monad but not valid instances of MonadRec? That is, what are some examples of monads which are not tail recursive?