Prove correctness of recursive algorithm
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).$$