Solving the Nurse Scheduling problem Is a major research area in Operations Research. Due to it being an NP-Hard problem, most researchers develop a heuristic solution for it The NSP has several constraints that need to be satisfied: several mandatory “hard” constraints that reflect hospital requirements, and several optional “soft constraints" that reflect the nurses' preferences. In this paper, we present a recursive solution to the problem that makes use of those constraints to shrink the search space and obtain results in a reasonable amount of lime. We present two variations of the solution. a nurse-by-nurse method of building the optimal schedule, and a shift-by-shift approach. Both variations were implemented and tested with various scenarios and the shift-by-shift solution provided much better results. The solution can also be modified easily to provide fair long-term scheduling,