Recursive version of Naidim's Answers.
find . -name "* *" | awk '{ print length, $0 }' | sort -nr -s | cut -d" " -f2- | while read f; do base=$(basename "$f"); newbase="${base// /_};"; mv "$(dirname "$f")/$(basename "$f")" "$(dirname "$f")/$newbase"; done