Build a table of solutions for n between 4 and 10, excluding 5. Do you see a pattern? In particular, do you see a way to produce solutions for larger values by modifying solutions for smaller values?
Try using more than one base case.