The recall is not to remove the cheating logic; it is to actually make the engines meet emissions requirements so they do not violate the law any more. From Autoblog's initial article on the scandal:
Volkswagen intentionally installed software in nearly a half-million diesel vehicles that helped the cars evade substandard results on emissions tests, the federal government charged Friday.
The Environmental Protection Agency issued a notice of violation to the German automaker, saying the company's software broke the law by violating two provisions in the Clean Air Act. Circumventing the standards meant affected cars emitted as much as 40 times the allowable level of certain pollutants.
Both the EPA and California Air Resources Board have launched investigations. In its notice of violations, the EPA said Volkswagen officials admitted to installing and concealing what they call a "defeat device," which was designed to detect when the cars were undergoing official emissions tests – and only turn on emissions controls during that time.
Some articles have suggested that the affected engines need more than just a software patch; hardware changes will be required (emphasis my own):
According to Automotive News citing Reuters, two remedies to cover different NOx-reducing systems could be necessary, and both potentially affect performance.
Earlier examples of the EA 189 diesel engine used a lean NOx trap to reduce the harmful material coming from the tailpipe. According to experts in the Automotive News report, a software update might allow the engines to achieve compliance, but that could affect fuel economy. VW already tried this route once before the scandal came to light, but tests by the California Air Resources Board still showed the figures were too high.
Later, some of the 2.0 TDI engines began using Selective Catalytic Reduction that reduced NOx by injecting a urea solution into the exhaust stream. According to Automotive News, a software update for this equipment might increase the amount of the substance used. Not only would that mean topping up the fluid more often, but there still could be some reduction in fuel economy. But, since the 2-liter, 4-cylinder TDI engine that sits inside the diesel vehicles first mentioned as being affected by the issue in the US don't have a urea treatment system, VW would need to install them into these cars.
The irony of this whole episode is that regulatory compliance would have been far, far cheaper.