I was thinking base fatigue recovery on magnitude, so the tireder you are the faster you recover.
- p.fatigue -= 1 + one_in(4);
+ p.fatigue -= 1 + x_in_y(p.fatigue, SLEEP_PER_DAY * 4);
The player accumulates 288 fatigue in 24 hrs, more fatigue than that makes for greater recovery rate, less makes for less, roughly in the range of 1.0 per tick to 2.0 per tick (probably won't actually reach 2.0).  The numbers aren't exactly comparable, right now when awake fatigue ticks up once every 5 minutes, and when asleep it ticks down by 1.5 every 5 minutes (since it's ticking up, then down every other 2.5 minutes).  This constant can be tweaked of course.