Which of the following is a poor application of naive recursion because it…

Concept

A recursive algorithm reduces a problem to smaller instances of the same problem and stops at a base case.

It is a good design when this decomposition follows the problem structure without repeatedly solving identical subproblems.

Application

1. For factorial, fact(n) = n × fact(n − 1) creates one chain of decreasing arguments and performs Θ(n) work.

2. For naive Fibonacci, F(n) = F(n − 1) + F(n − 2) creates two branches. The two branches repeatedly recompute values such as F(n − 2), so the work grows exponentially without memoization.

3. For Tower of Hanoi, the first recursive call moves the same set of n − 1 smaller disks to the auxiliary peg, and the second moves that set to the destination after the largest disk moves.

4. For depth-first tree traversal, recursion mirrors the tree: each node is processed once and each child subtree is visited once.

Cross-check and contrast

• Factorial has one smaller recursive subproblem at each level.

• Tower of Hanoi has an exponential number of required moves, so its recursive branching reflects the puzzle itself rather than avoidable repeated computation.

• Tree traversal follows the recursive structure of the data and takes Θ(n) time for n nodes.

Therefore, the poor application of naive recursion among the given choices is Fibonacci numbers; memoization or iteration removes the repeated work.