Five tasks. All of them about the same thing: where the stack lives.

---

1. MaxDepth(f *Folder) int

Returns the depth of the deepest folder. Write it both ways — recursive and iterative.

The iterative one has to hold (folder, depth) pairs. Why can the depth not be tracked separately from the folder?

---

2. WalkIterativeDepth(root *Folder) (items, maxStack int)

Extend the iterative traversal to also return the greatest stack depth it reached.

Run it on your tree and on a chain. In which case does the depth equal n? Why is it far smaller on a branching tree?

The recursive version cannot report this. Explain why.

---

3. Factorial and tail recursion

Write Fact(n int) int recursively, then rewrite it without recursion.

Some languages optimise this case away and use no stack at all. Go does not. Check: how deep does your Fact get before it dies? Compare with step 3's 119-byte frame.

---

4. Fibonacci and repeated work

Fib(n int, c *metrics.Counter) int — naive recursion, counting calls.

Run it for n = 10, 20, 30 and write down the numbers. The growth is not linear and not quadratic. Characterise it.

Then add a map[int]int of already-computed values. How many calls now?

---

5. When recursion is the right choice

Three steps have shown the iterative version to be faster and safer.

So why does anyone write recursion? Name a concrete case in your own algo project where recursion is plainly clearer, and work out the worst-case depth it could reach.

If the depth is bounded and known, recursion is the right answer. Show that it is.