Parallelization of an iterative function application
A good starting point is the Wikipedia article on Prefix Sums.  A particularly good source is Guy Blelloch's article about Prefix Sums.

The idea is this: if you have an associative operator (e.g., "+"), you can turn a long dependent chain of those operators into a tree that is more balanced.

For the example you gave, $f(x,y,z) = x + (y-x)/(z+1)$ we can actually generalize to an entire class of problems.
$$
\begin{array}{rcl}
x_{i+1} &amp; = &amp; x_i + (y_{i+1}-x_i)/(z_{i+1}+1)                                     \\
        &amp; = &amp; \frac{y_{i+1}}{z_{i+1}+1} + \frac{x_i (z_{i+1}+1) - x_i}{z_{i+1}+1} \\
        &amp; = &amp; \frac{y_{i+1}}{z_{i+1}+1} + \frac{z_{i+1}}{z_{i+1}+1} x_i           \\
        &amp; = &amp; a_{i+1} + b_{i+1} x_i\mathrm{,}
\end{array}
$$
where the $a_i$ and $b_i$ can be calculated completely in parallel.  So the calculation looks like:



Ok.  So let's look at a few iterations starting at $x_i$ through $x_{i+3}$:
$$
\begin{array}{rcl}
x_{i+2} &amp; = &amp; a_{i+2} + b_{i+2} x_{i+1}                                        \\
        &amp; = &amp; a_{i+2} + b_{i+2} (a_{i+1} + b_{i+1} x_i)                        \\
        &amp; = &amp; (a_{i+2} + a_{i+1} b_{i+2}) + b_{i+2}b_{i+1} x_i                 \\
x_{i+3} &amp; = &amp; a_{i+3} + b_{i+3} x_{i+2}                                        \\
        &amp; = &amp; a_{i+3} + b_{i+3} (a_{i+2} + a_{i+1} b_{i+2} + b_{i+2}b_{i+1}x_i)\\
        &amp; = &amp; (a_{i+3} + a_{i+2}b_{i+3}  + a_{i+1}b_{i+3}b_{i+2}) + b_{i+3}b_{i+2}b_{i+1}x_i\\
        &amp; = &amp; A_{i+1,i+3} + B_{i+1,i+3}x_i
\end{array}
$$

and so on.  The interesting thing is that we can calculate $x_{i+k}$ as $A_{i+1,i+k} + B_{i+1,i+k}x_i,$ where large chunks of computation can be summed up independently in the $A_{i+k}$ and the $B_{i+k},$ without knowing $x_{i+1}, \cdots, x_{i+k-1}.$

Now let's chunk up the work of calculating the $x_i$'s.  Here's what it might look like if we divided the calculation up into 4 equal parts and put each part on a different thread:



So each thread works completely independently to calculate the $A_i$ and $B_i$.  Then we have a final (sequential) phase where we calculate $x_{n/4}, x_{2n/4}, x_{3n/4},$ and $x_n$.

As Guy Blelloch's article shows, you can actually calculate all the partial sums with one last step, if you need them.