Challenge lab in Call Stacks and Recursion

Mission

Compute an integer power by halving the exponent.

Learning outcome: Design logarithmic exponentiation

Correctness contract

Invariant: Every recursive call moves strictly closer to a reachable base case.

Required technique: Compute one half-power recursively and square it, multiplying by the base only for an odd exponent.

Complexity target: time O(log exponent); space O(log exponent).

Input and output

Input: An integer base followed by a non-negative integer exponent. Whitespace may be spaces or line breaks.

Output: Print the single exact numeric result with no label. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• The exponent is non-negative.
• The exact result fits in a signed 64-bit integer.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Compute one half-power recursively and square it, multiplying by the base only for an odd exponent.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

2 10

Sample output

1024

Why the sample works: Visible walkthrough for the ordinary non-trivial path. One recursively computed half-power is squared and multiplied by the base only for an odd exponent. Input `2 10` therefore produces `1024`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: Store pow(base, exponent / 2) in a local variable and reuse it.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.