Why is N/k the effective number of parameters in k-NN? For the sake of completeness, $k$-nearest neighbor method classifies a point in space by comparing the average over the labels of $k$ nearest neighbors with $0.5$. 
The book Elements of Statistical Learning states [removed irrelevant text]$-$

It appears that the $k$-nearest-neighbor fits have a single parameter, the number of neighbors $k$. The effective number of parameters of $k$-nearest neighbors is $N/k$ and decreases with increasing $k$. To get an idea of why, note that if the neighborhoods were nonoverlapping, there would be $N/k$ neighborhoods and we would fit one parameter (a mean) in each neighborhood.

By fixing $k=k'$, every point in space has a fixed classification. There is no more parameter to learn. Similar argument follows that for each nonoverlapping neighborhoods, the mean is fixed.
So how are there $N/k$ parameters?
 A: To answer that, you need to ask yourself what a model is. For example, a simple univariate linear model $y = \beta_0 + \beta_1 x$, where you have 2 parameters $\beta_0, \beta_1$ and input data $x$. You can predict values by introducing new data into $x$ and exploiting the knowledge which consists of the linear relation and 2 parameters. No other knowledge is needed to predict, so it is fine to say that the parameters of the linear model are 2. No training data values are included into parameters, they are sublimated into the regression model parameters.
Now considering k nearest neighbor. Which is the model? You have something like the class index of maximum count from neighbor of input x. Now going on, if we further assume that the regions do not overlap (which is somehow a strong assumption, but does not affect the main idea), then you can conclude that in general you will have $n/k$ regions, and in each region you predict with a max count of the target variable. This max count is what is used for prediction, no other information is required. Your model (considering non overlapping regions) is something like $y = \sum_{r=1}^{n/k} argmax_k (count(y_j)) 1_{j \in region_r}$, where $1$ is indicator function equals with $1$ if $j \in region_r$, $0$ otherwise.
From that formalization, you can see that for each region you have a parameter which is fitted as $argmax_k$ so you can say that you have $n/k$ parameters, since those only are used for prediction (other that input $x$ which is not a parameter).
This can go further to an extreme case, for example consider $k=n$. In this case, we have a single region, for that region we fit a single parameter as the argmax index of the majority category.
The assumption for non overlapping regions looks rather strong, but it is used in order to simplify the calculus a lot.
A: Remember that 'parameter' is different in statistics; instead of merely an argument to a function, a parameter is a value that describes a population.
A: Hastie's other works (Generalized Linear Models book and Effective Degrees of Freedom paper) are more precise on the issue of "effective number parameters" aka "effective degrees of freedom."
The idea is that for linear parametric methods, the number of parameters is proportional to the expected gap between train and test error. Take the noise-scale-independent component of this quantity and call the result "effective parameters". This lets you "count parameters" even when there are no parameters to speak of. This view also explains why "effective number of parameters" of ridge regression depends on the value of $\lambda$
Relevant part from the Effective Degrees of Freedom (DF) paper:

I haven't seen the derivation of "DF" quantity for the nearest neighbor classifier, showing that DF is equal to $N/k$ for the case of nearest neighbor would answer the question.
There's a related result for "running mean smoother of $k$ observations" in Hastie's "Generalized Linear Models" book, section 3.3, showing that the number of effective parameters is $O(1/k)$
