Question: We have a REST API that works great. We're refactoring and deciding how to internally handle errors by the users of our API. 

For example the user needs to specify the "movie" url parameter which should take the value of "1984", "Crash", or "Avatar". First we check to see if it has a valid value. 

What would be the best approach if the movie parameter is invalid?

* return null from one of the internal methods and check for the null in the main API call method
* throw an exception from the internal method and catch exceptions in the main API method

I think it would make our code more readable and elegant to use exceptions. However, we're reluctant because we'd be potentially throwing many exceptions because of user API input errors, our code could be perfect. This doesn't seem to be the proper use of exceptions. If there are heavy performance penalties with exceptions, which would make sense with stack traces needing to be collected, etc., then we're unnecessarily spending resources when all we need to do is tell the user the parameter is wrong.

These are REST API methods, so we're not propogating the exceptions to the users of the API, nor would we want to even if possible.

So what's the best practice here? Use ugly nulls or use java's exception mechanism?

Answer: 
Neither.

The key is that passing a bad parameter isn't that exceptional a condition. Exceptions are thrown for exceptional circumstances. (That's the reason to not use them here, not the performance.)

You should be using something like Spring's DataValidation API for binding parameters that are passed in.

A client of a REST API should not be receiving null or exceptions. They should get an error message that gives them an idea of what's going on without exposing those details. "Sorry, we couldn't find that movie" or null? Go with the first, hands down.
I will assume that you are doing input validation here and in this case, your database will do a query for a safe string and it won't find the record since it don't exist in your database, ok?

If you are using any MVC framework the Model should throw already a RecordNotFound exception no? 

If you are always expecting to find a value then throw the exception if it is missing. The exception would mean that there was a problem.

If the value can be missing or present and both are valid for the application logic then return a null.

More important: What do you do in other places of the code? Consistency is important.