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?

Improve this question
$\endgroup$
1
  • 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$ Commented Jan 24, 2016 at 2:12

2 Answers 2

Reset to default
4
$\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).$$
Improve this answer
$\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. ;-)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.