State based vs State-less design (in verilog)
Even though a design may be considered 'stateless' because there is no explicit state machine, you may still be actually coding a type of state mechanism without explicitly calling it that. For example, flags may be used to indicate if one part of the code is busy or not. In your 'calculator' example, you may not have a state machine, but you may have a flag that indicates that data is available and ready for processing. Even though this may not be called a state machine, you are using flags or other signals as a mechanism to ensure that specific operations are performed in a certain sequence. You're essentially making a state machine using your flags. 

As a result, a state machine is pretty much present in most things. An explicitly designed one is really just a way for the coder behind the keyboard to keep track of the process their system is going through to ensure that everything performs as expected. When a system is more complicated, this is a really useful mechanism because it's only possible to keep track of so much at once. If it's a simple design, it may just be necessary to use a couple of flags and be done with it. It really just comes down to how complicated the problem is.