I'm in a first year discrete math course and we started algorithms. I created a recursive algorithm to multiply two numbers together:
function multiply($n, $r) {
if($n == 1)
return $r;
else if($r == 1)
return $n;
else
return $r + multiply($n - 1, $r);
}
How do I prove my algorithm is correct?
A quick google search tells me I have to prove that it works for $n + 1$ and I have to prove that it terminates. Unfortunately I'm still incredibly new to this and haven't the faintest clue as to where to start for proving my algorithm correct, so I would really appreciate some help here. I think maybe I have to do some sort of proof by induction but as this is an algorithm, I wouldn't know where to start.