Again, in discussions like this state is often used to refer to mutable state (an identical thing itself mutates).

Having a conceptual reference (oh god another overloaded term) to something does not imply that there is mutable state on the programming language as long as the reference is immutable.

    def times(x, y)
      if x.is_one?
        y
      elsif x.is_zero?
        x
      else
        y.add(times(x.decrement, y)
      end
    end

a) x and y are not mutated. b) you can implement the called methods on various immutable object types, and the code would work (assuming we send in the same types, and they obey certain protocols but that is yet another different concern):

    class WeirdString
      def init(v)
        @val = v
      end

      def val
        @val
      end

      def is_zero?
        @val.empty?
      end

      def is_one?
        @val.length == 1
      end

      def decrememt
        WeirdString.new(@val[0..-2])
      end

      def add(ws)
        WeirdString.new(@val + ws.val)
    end

    # times(WeirdString.new('abc', 'hi').val → 'hihihi'

Now, you may say the fact that the object has an instance variable means there is state and you'd be right depending on how you define state, but at any rate the state of a given instance of WeirdString is not mutable.