I'm a big fan of working out/walking on an empty stomach. I actually fast almost everyday until after my workouts. The fasts are usually 16-22 hrs depending on work and whatnot.
It's up to you and what feels right, basically. Are you riding/walking in the morning? Waking up and going out on an empty stomach might feel fantastic! Or after work to shake off the day and whatever you were dealing with might feel fantastic! I'm betting the majority of your responses will be to not eat before your exercise and eat when you feel hungry.
But whatever you do, congratulations on feeling better and getting moving!