Expected value uniform decreasing function We are given a function $f(n,k)$ as

for(i=0;i &lt; k;i++)
  n = rand(n);
return n;


rand is defined as a random number generator that uniformly generates values in the range $[0,n)$. It returns a value strictly less than $n$; also $\operatorname{rand}(0)=0$.

What is the expected value of our function $f(n,k)$ given $n$ and $k$?
I will make a guess that rand(n) returns uniform reals on the interval [0,n).
Since rand(n) gives the same distribution as n*rand(1). Thus for given $n$ and $k$ the random variable produced by the algorithm is
$$
   X = n \prod_{m=1}^k U_m
$$
where $U_m$ are independent identically distributed continuous uniform random variables on the unit interval. Thus
$$
   \mathbb{E}\left(X\right) = n \prod_{m=1}^k \underbrace{\mathbb{E}(U_m)}_{=\frac{1}{2}} = n 2^{-k}
$$


Responding to OP's request to consider the case when rand(n) returns unifrom random integers $[0,n]$. Let $Y_m \sim \mathcal{DU}\left([0,Y_{m-1}\right)$ be such a uniform random integer drawn on $m$-th iteration. Assume $Y_0 = n$. Then we seek to find
$$
    \mathbb{E}\left(Y_k\right) = \mathbb{E}\left( \mathbb{E}\left(Y_k \mid Y_{k-1}\right)\right) = \mathbb{E}\left(\frac{1}{2}Y_{k-1}\right) = \ldots =\frac{1}{2^k} Y_0 = \frac{n}{2^k}
$$ 
Thus the expectation is the same as in the case of continuous uniforms.


Now, assuming rand(n) generates uniform integers on $[0,n)$, instead of $[0,n]$. In that case $Y_k|Y_{k-1} \sim \mathcal{DU}\left( \left[0, \max(Y_{k-1}-1,0)\right]\right)$. Obtaining closed form is not feasible for arbitrary $k$, but with the help of Mathematica I was able to get expectations for low values of $k$:
$$ \mathbb{E}\left(Y_1\right) = \begin{cases}
 \frac{n-1}{2} &amp; n &gt; 1 \\[5pt]
 0 &amp; \text{otherwise}
\end{cases}
$$
$$
\mathbb{E}\left(Y_2\right) = \begin{cases}
 \frac{(n-1)(n-2)}{4 n} &amp; n&gt;2 \\[5pt]
 0 &amp; \text{otherwise}
\end{cases}
$$
$$
\mathbb{E}\left(Y_3\right) = \begin{cases}
 \frac{1}{8 n} \left(4 H_{n-1}+(n-1)(n-6)\right) &amp; n&gt;3 \\[5pt]
 0 &amp; \text{otherwise}
\end{cases}
$$
$$
   \mathbb{E}\left(Y_4\right) = \begin{cases}
 \frac{1}{16 n} \left( 4 \left(H_{n-1}\right){}^2+12 H_{n-1}-4 H_{n-1}^{(2)}+(n-1)(n-14) \right) &amp; n&gt;4 \\[5pt]
 0 &amp; \text{otherwise}
\end{cases}
$$

This is the reproducing code:

Block[{z, yc, ypr}, 
  Rest@NestList[(Piecewise[{{Expectation[(#1 /. z -&gt; yc), 
            Distributed[yc, 
             DiscreteUniformDistribution[{0, Max[ypr - 1, 0]}]], 
            Assumptions -&gt; Element[ypr, Integers] &amp;&amp; ypr &gt;= 1], 
           ypr &gt;= 1}}, # /. z -&gt; 0] /. ypr -&gt; z) &amp;, z, 4] /. z -&gt; n] //
  Simplify[#, Element[n, Integers] &amp;&amp; n &gt;= 0] &amp;


The rational part in the expectation appears to be $\frac{(n-1)(n+2-2^k)}{2^k n}$, thus in the large $n$ limit, expectation would agree with the continuous case. The expression involving harmonic numbers is of order $\mathcal{O}\left(\log(n)^{k-2}\right)$, and thus small compared to $n$.

With the guess-work, I was also able to find $\mathbb{E}(Y_5)$:
$$
  \mathbb{E}(Y_5) = [n &gt; 5 ] \left( \frac{(n-1)(n-30)}{32 n} + \frac{1}{32n} \ell_n \right)
$$
where 
$$
  \ell_n = -8 H_{n-1} H_{n-1}^{(2)}+\frac{8}{3} \left(H_{n-1}\right){}^3+12 \left(H_{n-1}\right){}^2+28 H_{n-1}-12
   H_{n-1}^{(2)}+\frac{16 }{3} H_{n-1}^{(3)}
$$
Here is confirmation with simulations:

In[153]:= 
With[{n = 17},
    (28 HarmonicNumber[n-1] + 12 HarmonicNumber[n-1]^2 + 
     8/3 HarmonicNumber[n-1]^3 - 12 HarmonicNumber[n-1,2] - 
     8 HarmonicNumber[n-1] HarmonicNumber[n-1,2] + 
     16/3 HarmonicNumber[n-1,3] + (n-1)(n-30))/(32 n)] // N

Out[153]= 0.131232

In[157]:= 
Table[Nest[RandomInteger[{0,Max[#1-1,0]}]&amp;, 17, 5], {10^7}] // N // Mean

Out[157]= 0.13157
If the random numbers are not restricted to integers but are uniformly generated on the entire interval $[0,n)$, the expected value is halved in each iteration, and thus by linearity of expectation the expected value of $f(n,k)$ is $2^{-k}n$.

If $n$ and the random numbers are restricted to integers, the expected value decreases from $a_i$ to $(a_i-1)/2$ in each iteration, so we need to shift by $1$ to obtain the recurrence $a_{i+1}+1=(a_i+1)/2$, so in this case the expected value of $f(n,k)$ is $2^{-k}(n+1)-1$.