Discrete Structure20825 marksProving correctness of recursive algorithms
Prove the correctness of following recursive algorithm for computing an using induction. ``` Power(a, n) { if (n = 0) return 1; else return a * Power(a, n-1); } ```
Prove the correctness of following recursive algorithm for computing $a^n$ using induction.
Power(a, n)
{
if (n = 0) return 1;
else return a * Power(a, n-1);
}
[5]
Claim: For all integers $n \geq 0$, Power(a, n) correctly returns $a^n$. --- When $n = 0$, the algorithm executes the branch: $$\text{return } 1$$ By definition of exponentiation: $$a^0 = 1 \quad \text{for any } a$$ The algorithm returns $1$, which equals $a^0$. ✓ The base case holds. --- Assume ...