Why need to declare output as a register in verilog
In Verilog a wire cannot store a value, it can only be used to connect two parts of a circuit together.

In order to be used in a procedural block (such as an always block, or initial block, etc.) a variable must be able to store a value, even if it is only during the processing of the block. As such you cannot assign a value to a wire within a procedural block because it cannot store a value.

In your case you are using your output in an always block, so your output cannot be a wire. If not specified to be otherwise an output is assumed to be a wire type. This is where your error occurs. In order to make the assignment in an always block you must therefore explicitly declare the output as a reg (i.e. output reg).



To expand on the point "Why do I need a register if this functionality can be implemented using combinational logic with primitives?":

Remember that Verilog is just a description language. You can declare things in many different ways, and not necessarily description just for FPGAs but also for simulation and other devices. As such what is inferred from the code is situation dependent.

An always block as far as Verilog is concerned is executed line by line, which means anything that is assigned within the always block must be able to store a value temporarily during the execution of the block, and depending on the code after execution as well. 

Whether or not this storage represents registers, latches, or just plain combinational logic depends on how it synthesises which is for the most part up to the synthesis tool and not something defined in the Verilog spec. This is why regardless of what happens in the block the Verilog spec simply mandates that any variable used in a procedural block must be able to store a value.



In response to your comment, there are non-procedural ways of doing things which do not require registers - any combinational circuit can be defined without the need for procedural blocks.

An example in your case would be to use the ternary operator with a continuous assignment statement:

assign O = SEL ? (A - B) : (A + B);


When SEL is 1, O is assigned (A-B), otherwise O is (A+B).