Recursion Practice: Merge a Prefix with Its Last Element¶
Problem setter's solution: recursively find a prefix maximum, then compare it with the last element. Codex (GPT-6): a clear interval interface and boundary proof, plus balanced recursion with reduced call depth.
Preferred recursion¶
Use zero-based, half-open intervals \([l,r)\) . If \(r-l=1\) , return the only element. Otherwise return
Start with \(M(0,n)\) . Pass the array by const reference, avoiding copies at each level.
A one-element interval is handled correctly. For a longer interval, recursion gives the maximum of its first \(r-l-1\) elements; comparing this with the last element yields the interval maximum. Induction on interval length proves correctness. Returning actual elements rather than initializing to zero handles all-negative inputs.
Cost and the recursion requirement¶
There are \(n\) recursive calls and \(n-1\) comparisons, taking \(O(n)\) time. The call chain has at most \(n\) levels and uses \(O(n)\) stack space; total space including the input array is also \(O(n)\) . The depth is suitable for \(n\le100\) .
std.cpp uses the recursively returned value in its maximum calculation and satisfies the implementation requirement. Output alone cannot verify recursion, so this exercise also needs source inspection.
Balanced interval recursion and alternative.cpp reduce call depth to \(O(\log(n+1))\) while retaining \(O(n)\) time. The lower auxiliary stack use makes this a parallel option. Both still store an \(O(n)\) input array, so the balanced implementation's total space is not logarithmic. Both pass all formal inputs.
See the test plan, generation instructions, and environment and measurements.