Pseudocode recursive function

Question

I'm studying for my midterm and one of the practise questions asks:

Consider the recursive pseudo algorithm Milk(a), which takes as an input integer a>=1.

MILK(a)
    if a = 1;
    then eat cookie;
    else drink glass of milk;
       select a random integer b with 1 <= b <= a-1
       MILK(b);
       MILK(a-b);
    endif

1) Explain why for any integer a>= 1 algorithm MILK(a) terminates

I think for this one because of the n-1, the possibility for m becomes smaller and smaller for the input into the recursive function MILK(b);, eventually reaching 1 which satisfies condition a = 1; therefore eating a cookie and so terminating the algorithm.

2) Let M(a) be the amount of glasses of milk you drink when running MILK(a). Determine the exact value of M(a)

For this one I assume it will be M(a) = a + a, since every time you run it 'a' is the input and adding every input together will give you the total.

How are my answers looking? Or this completely incorrect. Thank you!

Answer 1

For the second question, you could use the law of total probability (transferred to expected values - you possibly have to search for this).

M(a) denotes the number of glasses (as you suggested), E() is the expected value of something. This law of total probability then yields:

E(M(a)) = sum(E(M(a) | b=i) * Pr(b=i), i=1..a-1) =
        = ... =
        = 1/(a-1) * (1+sum(E(M(i)+M(a-i), i=1..a-1)))

As far as I understood, the base case M(1)=0 holds.

If you transform the above recurrence relation and try it out (e.g. in a small python program), you should be able to recognize a simple pattern that possibly can be proven via induction.

Answer 2

The first answer is fine.

The second, however, is not. Consider a=1. Your answer is two glasses or milk, whereas the correct answer is zero. Hint: Try working through some small examples by hand to get a feel for what's going on in the algorithm.