Base case: Recursive cases: - If is even: - If is odd: python def power(x, n): if n == 0: return 1 if n % 2 == 0: half = power(x, n // 2) return half * half else: return x * power(x, n - 1) Tracing power(2, 10): plaintext power(2, 10) → even: power(2, 5)² power(2, 5) → odd: 2 × power(2, 4) power(2, 4) → even: power(2, 2)² power(2, 2) → even: power(2, 1)² power(2, 1) → odd: 2 × power(2, 0) power(2, 0) = 1 Only calls instead of !
Time complexity is instead of . Space complexity is for the call stack.