bzip されていないすべてのファイルを再帰的に bzip2 するにはどうすればよいですか?

find はあなたの友達です。次のようにすればよいと思います:

find <target_dir> -not -name \*.bz2 -exec bzip2 \{\} \;

つまり、bzip するファイルがあるディレクトリが /var/log/blah の場合、次のようになります:

find /var/log/blah -not -name \*.bz2 -exec bzip2 \{\} \;