Frozen in this condition for hours. Increasing memory use between 1 and 10 MB per second. Finally I terminated. Didn't expect it to find this many files (I only deleted about 3 thousand). Perhaps it tries to sort them (may I suggest quicksort)? If so, why when I only asked for a very specific filename?
In my case this was caused by a hidden confirmation dialogue box asking for renaming duplicate-name files. Try ALT-TAB to circle through your open applications. Recuva didn't show preview icons for two windows in the task pane that could have indicated that there was a recuva-related second window/popup open.