This paper presents an accurate and robust surgical instrument recognition algorithm to be used as part of a Robotic Scrub Nurse (RSN). Surgical instruments are often cluttered, occluded and displaying specular light, which cause a challenge for conventional vision algorithms. A learning-through-interaction paradigm was proposed to tackle this challenge. The approach combines computer vision with robot manipulation to achieve active recognition. The unknown instrument is firstly segmented out as blobs and its poses estimated, then the RSN system picks it up and presents it to an optical sensor in an established pose. Lastly the unknown instrument is recognized with high confidence. Experiments were conducted to evaluate the performance of the proposed segmentation and recognition algorithms, respectively. It is found out that the proposed patch-based segmentation algorithm and the instrument recognition algorithm greatly outperform their benchmark comparisons. Such results indicate the applicability and effectiveness of our RSN system in performing accurate and robust surgical instrument recognition.