Expected value of a recursive random function

Question

   function foo(n)  
     if n = 1 then  
        return randint(INT_MAX)
     else  
        return randint(foo(n-1))
     end if  
   end function

The idea is that the function recursively decides the next maximum value for an random integer.

If foo is initially called with m as the parameter, what is the expected value of the output? Also is it possible to plot a rough distribution function?

BTW, randint(n) returns a uniformly distributed random integer in the range 0 to n.

Few examples for m = 10 and INT_MAX = 2^31-1:

0: 1773222062
1: 302320327
2: 217321806
3: 167172143
4: 16407259
5: 11236721
6: 10246171
7: 7399283
8: 2797307
9: 450964
10: 65659

0: 758108310 
1: 496236452 
2: 339520617 
3: 254288094 
4: 109227996 
5: 44669101  
6: 41496117  
7: 18575039  
8: 826387    
9: 207751    
10: 170187   
```

Answer 1

Let $\mu = $ MAX_INT. Let $E_n[\mu]$ be the desired expected value of foo$(n)$. We have $E_1[\mu]=\frac {\mu}2$ and $E_n[0]=0$

For a general $n$ we have $E_n[\mu]=\frac 1{\mu+1} \sum_{i=0}^{\mu} E_{n-1}[i]$

It is a simple matter to confirm that $$E_n[\mu]=\frac {\mu }{2^{n}}$$ satisfies this recursion and the initial conditions, so we are done.