Parallel solution of recurrence equation
For linear recurrences, you may find interesting this recent work:

Adrian Nistor, Wei-Ngan Chin, Tiow-Seng Tan, and Nicolae Tapus. 2009. Optimizing the parallel computation of linear recurrences using compact matrix representations. J. Parallel Distrib. Comput. 69, 4 (April 2009), 373-381. DOI=10.1016/j.jpdc.2009.01.004 http://dx.doi.org/10.1016/j.jpdc.2009.01.004

A discussion of the parallel complexity of solving recurrences is available in

Oscar H. Ibarra and Nicholas Q. Tr\&amp;#226;n. 1994. On the Parallel Complexity of Solving Recurrence Equations. In Proceedings of the 5th International Symposium on Algorithms and Computation (ISAAC '94), Ding-Zhu Du and Xiang-Sun Zhang (Eds.). Springer-Verlag, London, UK, 469-477.

Hope this helps.