fun pow(0) = 1
| pow(n) = pow(n - 1) + pow(n - 1)
computes 2n. The function
local
fun helper(0, p) = p
| helper(n, p) = helper(n - 1, n * p)
in
fun fac(n) = helper(n, 1)
end
computes n!
Question
What does the Java method
public static int m(int i)
{
if (i == 0)
{
return 1;
}
else
{
return m(i - 1) + 2 * m (i - 2);
}
}
return? Which expression does it correspond to? How can induction
be used to prove the method correct?