The task doesn't seem too different from that done by File::Find or any other treewalking program.

How about keeping partial solutions on a stack? Backtrack with pop, go forward with push. You could implement that with recursive calls and let the stack be local and mainly implicit in the return conditions.

I don't know if that could be called functional programming. It is pretty much how functional languages work under the hood.