Recursion with Random number?    function foo(n)  
     if n = 1 then  
        return 1  
     else  
        return foo(rand(1, n))  
     end if  
   end function  

If foo is initially called with m as the parameter, what is the expected number times that  rand() would be called ? 
BTW, rand(1,n)  returns a uniformly distributed random integer in the range 1 to n.
 A: This is very similar to user44197's answer. 
Let $G(m)$ be the expected numbers of total calls to rand when foo(m) is executed.
We see that $G(1)=0$ and $G(2)=1 + G(2)/2 \implies G(2)=2$
For $m>2$ there are two possible events: that the first rand() returns the same number m (probability $m$), or not. In the second case, the follow-up is equivalent as if the argument m-1 were passed.
Hence  $$G(m) = \frac{1}{m}(G(m)+1) +  \frac{m-1}{m} G(m-1)$$
So
$$G(m)=G(m-1)+\frac{1}{m-1}$$
Eg $G(3)=2 + 1/2$, $G(4)=2 + 1/2 + 1/3$, or
$$G(m) = 1 + H_{m-1}$$ 
where $H_n$ is the harmonic number.
A: If $N(n)$ is the expected number of calls to foo, then for $n>1$
$$N(n) = 1 + \frac{N(1)+N(2)\cdots N(n)}{n} \Rightarrow N(n) =\frac{n}{n-1} +\frac{N(1)+N(2)\cdots N(n-1)}{n-1} $$
because each recursive call passes a random argument between 1 and $n$.
Starting with $N(1)$, calculate $N(2)$ etc to see the pattern.
The number of calls to rand is one less than the number of calls to foo.
A: It is better to reformulate the problem. Let $X_n$ be a sequence of random variables:
$$
     X_n \mid X_{n-1} \sim \mathcal{D}\left(1,X_{n-1}\right), \quad X_0 = m
$$
where $\mathcal{D}\left(p,q\right)$ denotes discrete uniform distribution of the domain $p \leqslant X \leqslant q$. Furthermore, define the stopping time:
$$
   N = \{n \colon \{X_n = 1, X_{n-1} > 1 \} \}
$$
The stopping time is a random variable. We seek to compute $\mathsf{E}(N)$.
Notice that
$$\begin{eqnarray}
   \Pr(N=n) &=& \Pr\left(X_n = 1, 1 < X_{n-1} \leqslant X_{n-2} \leqslant \ldots \leqslant X_0 = m \right) \\ &=& 
   \sum_{i_1 = 2}^{m} \sum_{i_2 = 2}^{i_1} \cdots \sum_{i_{n-1}=2}^{i_{n-2}} \Pr(X_n=1, X_{n-1}=i_{n-1}, \ldots, X_1=i_1 ) \\ &=& 
   \sum_{i_1 = 2}^{m} \sum_{i_2 = 2}^{i_1} \cdots \sum_{i_{n-1}=2}^{i_{n-2}} \frac{1}{m \cdot i_1 \cdot i_2 \cdots i_{n-1}}
\end{eqnarray}
$$ 
Then the expectation equals $\mathsf{E}(N) = \sum_{n=1}^\infty n \Pr(N=n)$. I do not expect a closed form for $\Pr(N=n)$, but the other answer provides a solution for $\mathsf{E}(N)$, which has an analytic expression:
$$
   \mathsf{E}(N) = \begin{cases} 0 & m = 1 \cr H_{m-1} + 1 & m > 1 \end{cases}
$$
You may find the following related problem useful.
Added: With a little bit of experimenting the following closed-form result seems to hold true for $\Pr(N=n)$:
$$
   \Pr(N=n) = (m-1) \sum_{k=0}^{m-2} (-1)^k \binom{m-2}{k} (k+2)^{-n}
$$
In[109]:= pr[m_Integer, 1] := 1/m;
pr[m_Integer, n_Integer /; n > 1] := Module[{it = Array[k, n - 1]},
  Sum @@ {Power[Times @@ it, -1]/m, 
    Sequence @@ Thread[{it, 2, Most[Prepend[it, m]]}], 
    Method -> "Procedural"}]

In[145]:= 
Table[pr[m, n] - (m-1) Sum[(-1)^k Binomial[m-2, k] (k+2)^-n, {k, 0, m-2}], 
     {m, 2, 8}, {n, 1, 16}] // Flatten // Union

Out[145]= {0}

With this result the expectation follows
$$ \begin{eqnarray}
   \mathsf{E}(N) &=& \sum_{n=1}^\infty n \Pr(N=n) = (m-1) \sum_{k=0}^{m-2} (-1)^k \binom{m-2}{k} \sum_{n=1}^\infty n (k+2)^{-n} \\
   &=& (m-1) \sum_{k=0}^{m-2} (-1)^k \binom{m-2}{k} \frac{k+2}{(k+1)^2} \\
  &=& (m-1) \sum_{k=0}^{m-2} (-1)^k \binom{m-2}{k} \left( \frac{1}{k+1} + \frac{1}{(k+1)^2} \right) \\ &=& (m-1) \int_0^1 (1-t)^{m-2} \mathrm{d}t + (m-1) \int_0^1 \frac{1}{t} \int_0^u (1-u)^{m-2} \mathrm{d}u \mathrm{d}t \\ &=& 1 + H_{m-1}
\end{eqnarray}
$$
