Previous post within category using Recent Posts

I am trying to have a link on index.php that points toward the previous post within the same category.

I know the prev_post code does not work on index.php, but have been using Recent Posts modified as described here. I am just looking for a way to have the previous link be category specific.

If there’s a way to do this, help would be appreciated.

Thanks.