I use:
for f in *\ *; do mv "$f" "${f// /_}"; done
Though it’s not recursive, it’s quite fast and simple. I’m sure someone here could update it to be recursive.
The ${f// /_}
part utilizes bash’s parameter expansion mechanism to replace a pattern within a parameter with supplied string.
The relevant syntax is ${parameter/pattern/string}
. See: https://www.gnu.org/software/bash/manual/html_node/Shell-Parameter-Expansion.html or http://wiki.bash-hackers.org/syntax/pe .