Draw the recursion trace for the execution of function Puzzle Solve(3,S,U) (Code Fragment 3.44), where S is empty and U = {a,b,c,d}.

Code Fragment 3.44

Solving a combinatorial puzzle by enumerating and testing all possible configurations. In Figure 3.21, we show a recursion trace of a call to PuzzleSolve(3,S,U), where S is empty and U = {a,b,c}. During the execution, all the permutations of the three characters are generated and tested. Note that the initial call makes three recursive calls, each of which in turn makes two more. If we had executed PuzzleSolve(3,S,U) on a set U consisting of four elements, the initial call would have made four recursive calls, each of which would have a trace looking like the one in Figure 3.21.