Comment by aparent

It is a bit more complicated then that. The only penalty to time is a constant factor if you are willing to use space proportional to the computation time. I did a bit of work on how to do time-space trade-offs in reversible circuits in my masters thesis http://hdl.handle.net/10012/10949.