What is the difference between regression and classification? What is the difference between regression and classification, when we try to generate output for a training data set $x$?
Regression: the output variable takes continuous values.

Classification: the output variable takes class labels.
It is important to be clear when using terms like regression, classification and prediction to discriminate between the task you are performing and the method used to perform it. A classification task involves taking an input and labelling it as belonging to a given class, so the output is categorical. On the other hand, a prediction task involves predicting a continuous valued output.

Methods for achieving these tasks include regression, in which a continuous valued output is estimated (or, rather, the expected value of a distribution on a continuous variable is estimated, conditional on a given set of input values). This can be used to carry out a prediction task, as you would expect. It can also be used to carry out a classification task, for example using logistic regression to estimate the log odds of the input pattern belonging to a given class. In this case, the task is classification, the method is regression.

Classification methods simply generate a class label rather than estimating a distribution parameter. K nearest neighbour is a good example where the task and the method are both called classification.