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_', ''))