Is the following recurrence for this program's runtime correct?
tl;dr: NO.  Well, okay, maybe.

Translating the pseudocode mechanically into a recurrence gives me
$$
T(n) = \Theta(1) + F(n) + \max \begin{cases}
    \max_{0\le s \le n/4} T(s) \\
\\
    \max_{n/4 &lt; s &lt; n} (T(s) + T(n-s))
\end{cases}
$$
where $F(n)$ is the time for the first "find" step.  Every outcome that is not known in advance is folded into the $\max$; since we're bounding the worst-case running time, we always assume the worst possible outcome.  The initial $\Theta(1)$ includes all the time for bookkeeping, comparisons, stack manipulation, and that union operation in the output.  (Performing a set union in constant time is somewhat magical, but I'll let that slide.)  I'm also assuming here that the variable $s$ always lies between $0$ and $v-1$, since otherwise the algorithm never terminates, although this assumption is never specified in the code.  

Under the reasonable assumption that $T(n)$ is monotonically increasing, we have
$$
\max_{0\le s \le n/4} T(s) = T(n/4)
$$
Under the further assumption that $T(n)$ is "nice" and convex, we have
$$
\max_{n/4 &lt; s &lt; n} (T(s) + T(n-s)) =
 \begin{cases}
 T(n-1) + T(1) &amp; \text{if $T$ is convex}\\
 T(n/4+1) + T(3n/4-1) &amp; \text{if $T$ is concave}
 \end{cases}
$$
Here, "convex" means that $(T(a) + T(b))/2 \ge T((a+b)/2)$ for all $a$ and $b$, or less formally, that the function "curves upward".  If $T$ is "nice", this is equivalent to assuming $T(n) = \Omega(n)$.  Symmetrically, $T$ is concave (curves downward) iff $T(n) = O(n)$.

("Nice" means a function whose second derivative is well-defined and doesn't oscillate between positive and negative forever; for example, the product of a polynomial and some logarithms is nice.  Wacky functions like $n^{2 + \sin(2\pi n)}$ are not nice, but I'll bet you a dollar that your algorithm doesn't have that function as a time bound.)

So our recurrence is now
$$
T(n) = \Theta(1) + F(n) + \max\begin{cases}
 T(n/4) \\
 T(n-1) + T(1) \\
 T(n/4 + 1) + T(3n/4 - 1)
\end{cases}
$$
If $T$ is increasing, the first case is smaller than the other two, so we can ignore it.  So we have two possibilities to consider.

First, suppose
$$
  T(n) = \Theta(1) + F(n) + T(n-1)
$$
(I folded the extra $T(1)$ into the $\Theta(1)$ term.)  This recurrence unrolls into a simple summation
$$
  T(n) = \Theta(n) + \sum_{i=1}^n F(i) 
$$
which implies that $T(n)$ is convex no matter what function $F(n)$ is.  So this  recurrence seems to work.  (The apparently circular argument about convexity can be unwound into a boring and mechanical proof by induction, if you care.)

On the other hand, suppose
$$
  T(n) = \Theta(1) + F(n) + T(n/4 + 1) + T(3n/4 - 1).
$$
Then even with the very strong assumption that $F(n) = O(1)$, a quick recursion tree argument implies that $T(n) = \Theta(n)$.  The same recursion tree argument implies that if $F(n)$ is grows even slightly faster than a constant, then $T(n)$ is strictly convex, which means this is the wrong recurrence.

So this recurrence only works when $F(n) = O(1)$.  In that case, we can simplify the recurrence further to
$$
  T(n) = \Theta(1) + T(n/4 + 1) + T(3n/4 - 1).
$$
We still have those pesky off-by-ones in the recursive arguments, but whatever.  We've already figured out that $T(n) = \Theta(n)$, so who cares about the recurrence any more?