Pseudo-code recursive function

Question

I study my middle age, and one of the practice questions asks:

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

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, the MILK (a) algorithm completes

I think that for this, because of n-1, the possibility for m becomes less and less for input into the recursive function MILK (b); ultimately reaches 1, which satisfies the condition a = 1; therefore there is a cookie and thus completes the algorithm.

2) Let M (a) be the number of glasses of milk you drink while working MILK (a). Determine the exact value of M (a)

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

? . !

Answer 1

( - , , ).

M(a) ( ), E() - -. :

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)))

, M(1)=0.

(, python), , .

Answer 2

.

-, . a=1. - , . . , , .

Answer 3

, , , a 1, , milk()? ?

b < a
a-b < a
MILK(1) returns (no recursion)

, . .

, , , , b = 1, b = 2, b = a/2 b = a-1?

, .

, MILK (v), MILK (v) = formula (v).

MILK (3), (4), (5), (9),

, Ruby ,

rdm = Random.new
def milk(a)
    if(a==1) then
        print "eat cookie\n";
    else
        print "drink milk\n";
        b = Random.rand(1..a-1)
        print "rand (1,#{a-1}) #{b}\n";
        milk(b)
        milk(a-b)
    end
end
ARGV.each { |argi| milk(argi.to_i); }

Answer 4

Tip. Calculate the first few values ​​of M (a). Get an idea for a closed formulas. Prove by induction.

The next hint: do you think the value depends on each choice b?