I have the same issue, where I want to replace the white space in any pdf file to a dash -. But the files were in multiple sub-directories. So, I had to use os.walk(). In your case for multiple sub-directories, it could be something like this:
import os
for dpath, dnames, fnames in os.walk('/path/to/directory'):
for f in fnames:
os.chdir(dpath)
if f.startswith('cheese_'):
os.rename(f, f.replace('cheese_', ''))