Frithjof,

I don't know what you consider simple, but I've done what your asking for in the past.  It was harder than I initially thought.  There are many recursion formula available, but they can't just be applied without some thought up front.  Otherwise, you will encounter divisions by zero or other unpleasant things.  

First, I believe that, because of your use of minus signs, you're intending that m and n be non-negative integers.

We can start with the following identity:

P_{-n}^{-m}(x) = P_{n-1}^{-m} (x) for n=1,2,3,...

Using this, the problem reduces to computing P_n^{-m}(x) for n=0,1,2,...

I will address the case where m can be any non-negative integer (not restricting it to m >= n).  The attached is an excerpt from a document I wrote a while back that will work. Just ignore anything mentioning derivatives. Also, reference [3] is

http://en.wikipedia.org/wiki/Associated_Legendre_polynomials#Orthogonality.

I hope that helps.

yes recurrencevrealtions u will find in any book