“Recent posts in [category]”

In my current blog template, if (is_single()) the sidebar displays a list of “Recent posts”: the last five things I’ve posted to my blog. What I’d like to have is a list of the last five posts in whatever category the post being viewed is in.

For example, when viewing a post about music, the “Recent posts” list would display the last five posts in the “music” category, preferably headed with “Recent posts in music”. Ideally, this wouldn’t break if posts are in multiple categories; in a perfect, shiny world, it would display a list for each category.

Any pointers?