Recurrence relations whose base case is 'at infinity' I ran across this recurrence relation in
a paper by Medina and Zeilberger [MZ]
(who got it from [CR]):
$$f(h,t) = \max \left( \frac{1}{2} f(h+1,t) + \frac{1}{2} f(h,t+1) ,\frac{h}{h+t} \right) \;.$$
The "base" condition of the recurrence is that,
for $h+t = \infty$, $f(h,t)=\frac{1}{2}$.
This function $f$ represents the expected gain in a paricular
coin game ($h$ and $t$ are heads and tails),
explained in this MSE posting.
I had not before encountered recurrence relations whose
"initial conditions" are "at infinity," and was surprised to learn
that there is no known explicit solution for $f$.
(However, one can compute particular values
numerically by limiting to $n$ trials and letting $n \rightarrow \infty$.  For example,
$f(5,3) =\max ( 0.62361957757, 5/8 )$.
See [W].)
My question is:

Is there a class of recurrence relations that includes the above
example, and for which some theory has been developed for solving
such equations?

Thanks for pointers and references!
References
[MZ]
Luis A. Medina, Doron Zeilberger,
"An Experimental Mathematics Perspective on the Old, and still Open, Question of When To Stop?"
arXiv:0907.0032v2 [math.PR]
[CR] Y.S. Chow and Herbert Robbins. On optimal stopping rule for $S_n/n$.
Ill. J. Math., 9:444–454, 1965.
[W]
Julian D.A. Wiseman
web page.
 A: For this specific recurrence, Olle Häggström and I have some results in the paper 
arXiv:1201.0626 [math.PR] that we just posted.
The key lemma is based on Olle's trick that I also mentioned in an answer to 
this question. 
Briefly, the argument is this (see our abstract or the link in the OP for a description of the game): If at some point in the game we condition on the event of ever reaching a proportion of (at least) $p$ of heads, then as long as we haven't, the conditional probability of heads in the next toss is at least $p$. Now, one way of showing that an event is unlikely is to show that strange things happen if we condition on it. If the conditional probability of a long run of heads is very different from the unconditional one, then the probability of ever reaching proportion $p$ of heads must be small.    
After pursuing the calculations, our main result (in the notation of the OP) is
$$f(h,t) \leq \max\left(\frac{h}{h+t}, \frac12\right) + \min\left(\frac14\sqrt{\frac{\pi}{h+t}}, \frac1{2\cdot\left|h-t\right|}\right).$$
This allows us to compute $f(h,t)$ to any desired precision, and to verify rigorously that $f(h,t) = h/(h+t)$ in a number of cases. For instance, $f(5,3) = 5/8$, which means that in the Chow-Robbins coin flipping game, stopping is optimal with 5 heads and 3 tails.
