1
$\begingroup$

I have this java function:

public int foo(ArrayList l, int n)
{
  if(n <= 1)
    return l.get(0);

  if(l.get(0) < l.get(1))
    l.remove(1);
  else
    l.remove(0);

  foo(l, n-1);
}

So I figure to show that the algorithm is correct I would use an induction proof. However what I am not so sure about is how to go about doing the proof. Will I fist need to derive some sort of mathematical formula for this function and prove that?

$\endgroup$
  • 2
    $\begingroup$ Prove for what? What is the function foo expected to do? We can only guess that foo is searching for the minimum number. $\endgroup$ – hengxin Jan 24 '16 at 2:12
3
$\begingroup$

Generally, you should follow the instructions given by @vonbrand to carry out a mathematical induction proof for a recursive algorithm. Now I would like to show you more hints.


Playing with a small test case, we know that we should prove the following theorem:

Theorem: The function foo always returns the minimum value of the original list $l$.


To carry out a mathematical induction on the size $n$ of list, we go through the following three steps:

  • Base Case: $n = 1$. In this case, you obtain $l[0]$ which is trivially the minimum. (Note that foo throws an exception for case $n = 0$.)
  • Inductive Hypothesis: Suppose that the theorem holds for $2 \le n \le k$.
  • Inductive Step: Consider $n = k + 1$. You should prove that (This is left as an exercise) $$\min(\text{modified list } l' \text{ by the `if/else` statement and of size } k ) = \min(\text{original list } l \text{ of size } k+1).$$
$\endgroup$
1
$\begingroup$

The way to understand a recursive program is by the following steps:

  • Find some measure by which the recursive calls are for "smaller" instances of the problem.
  • Show that when it reaches the smallest instances, it gives the correct result (directly)
  • Assuming the recursive calls do their job correctly, their results are combined to get the correct solution for the overall problem.

You should try some (small) cases by hand, to see what is going on (and find clues on the above points). When writing a recursive program, you'll have to think about the above items exactly the same way.

A correctness proof will have to consider essentially the same points, just more formally. No "mathematical formulas" are needed, just clear reasoning.

In your case, $n$ is an obvious measure of "size", that gets reduced each call. The rest is left as an exercise. ;-)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.