Solve recurrence relation that depends on depth of recursion
diplodoc explained in the comments one way to solve the recursion. Your recursion is
$$
A_n = 1 + \frac{A_0 + \cdots + A_{n-1}}{n+1}, \quad A_0 = 1.
$$
The trick is to calculate
$$
(n+1)A_n - n A_{n-1} = (n+1 + A_0 + \cdots + A_{n-1}) - (n + A_0 + \cdots + A_{n-2}) = 1 + A_{n-1},
$$
and so $A_n = A_{n-1} + 1/(n+1)$. From here it follows easily that $A_n$ is the $(n+1)$th harmonic number.



Another possibility is to use generating functions. Let
$$
P(x) = \sum_{n=0}^\infty A_n x^n.
$$
Since $\frac{1}{1-x} = 1 + x + x^2 + \cdots$, it follows that
$$
\frac{xP(x)}{1-x} = \sum_{n=0}^\infty (A_0 + \cdots + A_n) x^{n+1}.
$$
Integrating, we get
$$
\int_0^x \frac{yP(y)}{1-y} \, dy = \sum_{n=0}^\infty \frac{A_0 + \cdots + A_n}{n+2} x^{n+1}.
$$
It follows that
$$
\frac{1}{1-x} + \frac{1}{x} \int_0^x \frac{yP(y)}{1-y} \, dy = P(x).
$$
In terms of $Q(x) = \int_0^x \frac{yP(y)}{1-y} \, dy$, this reads
$$
\frac{1}{1-x} + \frac{Q(x)}{x} = \frac{(1-x)Q'(x)}{x},
$$
which simplifies to
$$
\frac{x}{1-x} + Q(x) = (1-x)Q'(x) = [(1-x)Q(x)]' + Q(x),
$$
and so
$$
(1-x)Q(x) = \int^y \frac{y}{1-y} \, dy = \int^y \left(\frac{1}{1-y}-1\right) \, dy = C - x - \log(1-x).
$$
It follows that
$$
Q(x) = \frac{C-x-\log(1-x)}{1-x}.
$$
Since $Q(0) = 0$, we deduce $C = 0$.
Differentiating and multiplying by $(1-x)/x$, we find that
$$
P(x) = \frac{-\log(1-x)}{x(1-x)} = \frac{\sum_{n=0}^\infty x^n/(n+1)}{1-x},
$$
from which we can extract the coefficient of $P(x)$ to be $H_{n+1}$.



Finally, we can solve this without using any recurrences. Consider a random permutation of the numbers $1,\ldots,n+1$, which we think of as the $n$ places and the goal. The frog jumps to the first number. If it is not $n+1$, it scans the list to the first larger number, and jumps there. Repeat in this way, until you get to $n+1$. You can check that this defines the same random process.

Given a permutation, the number of jumps is the number of left-to-right maxima, that is, elements which are larger than all that precedes them. The probability that the $i$th number is a left-to-right maximum is exactly $1/i$, and so linearity of expectation shows that the expected number of jumps is $1 + 1/2 + \cdots + 1/(n+1)$.



As a bonus, the last solution allows us to calculate higher moments of the distribution. The main observation is that the indicator variables $X_i$ for the $i$th number being a left-to-right maxima are independent Bernoulli random variables. This implies that the variance of the number of left-to-right maxima is
$$
\sum_{i=1}^{n+1} \frac{1}{i} \left(1-\frac{1}{i}\right) = H_{n+1} - \sum_{i=1}^{n+1} \frac{1}{i^2} = H_{n+1} - \frac{\pi^2}{6} + O\left(\frac{1}{n}\right).
$$

One checks that the central limit theorem applies, and so the total number of left-to-right maxima is asymptotically normal.



Why is the answer roughly $\log n$? One might expect the answer to be closer to $\log_2 n$, since at each step, $n$ is roughly cut in half. However, this argument assumes that the changes to $n$ are additive, whereas in reality they are multiplicative. It is better to consider instead the effect of each step on $\log n$. If $m$ is the new value of $n$, then the expected value of $\log m$ is
$$
E[\log m] = \frac{\log 1 + \cdots + \log n}{n+1} \approx \frac{1}{n}\int_0^n \log x \, dx = \left.\frac{1}{n} (x\log x-x)\right|_0^n = \log n - 1.
$$
Therefore the value of $\log n$ decreases by roughly 1 each step, and so we expect the number of steps to be around $\log n$ rather than $\log_2 n$.

(With some work, this intuition can be made rigorous.)