Recover/Reset MySQL root Password

Step1 : Stop mysql service

# /etc/init.d/mysqlsd stop

Step 2: Start to MySQL server without password:
# mysqld_safe --skip-grant-tables &
Output:

[1] 5988
Starting mysqld daemon with databases from /var/lib/mysql
mysqld_safe[6025]: started

Step 3: Connect to mysql server:
# mysql -u root
Output:

Welcome to the MySQL monitor. Commands end with ; or \g.
Your MySQL connection id is 1 to server version: 4.1.15-Debian_1-log
Type 'help;' or '\h' for help. Type '\c' to clear the buffer.
mysql>

Step 4: Setup new MySQL root user password
mysql> use mysql;
mysql> update user set password=PASSWORD("NEW-MySQL_ROOT-PASSWORD") where User='root';
mysql> flush privileges;
mysql> quit

Step 5: Stop MySQL Server:
# /etc/init.d/mysql stop
Output:

Stopping MySQL database server: mysqld
STOPPING server from pid file /var/run/mysqld/mysqld.pid
mysqld_safe[6186]: ended
[1]+ Done mysqld_safe --skip-grant-tables

Step 6: Start MySQL server:
# /etc/init.d/mysqld start
# mysql -u root -p

and now you can log in with your new password!