I have formatted a disc by accident and lost data

First thing to do is a copy of partition on another USB key, to have a backup.
For this boot on Ubuntu CD, "Try without install" and System->Administration->Gparted, and copy/paste partition from one USB key to the other one.
After that, a tool like photorec can help you to recover data.
There are other tools, but I don't know them.

restore from backup is definately going to be the option with guarunteed data integrity. If there data is "important" it will be backed up.

You can use foremost on the disk to see if it can retrive the data but the files recovered may be damaged. You will need a partition mounted or remote storage mounted as writable to extract the files to but your backups will certainly be your best bet.

http://en.wikipedia.org/wiki/TestDisk

Scalpel is one of the best command line tool to recover deleted files in Ubuntu Linux. It can recover almost all types of files. It visits data blocks of files sequentially and identifies deleted files and recovers them instantly. You can install it by running following command in your terminal.

apt-get install scalpel

Once installation is complete, you can start to recover your deleted data by using a simple command. Run the following command in terminal to recover your data.

scalpel /dev/sda1 -o output

where ‘output’ is the name of directory in which scalpel places the recovered files. You can specify any name to this directory, just make sure that this directory should not exist in your system because Scalpel create directory itself. Check the following snapshot to get an overview of how Scalpel searches deleted file.