The Kontsevich recursion formula is not special to $\mathbf{CP}^2$. It is a particular application of the more general associativity formula for quantum cohomology, which is something true for symplectic manifolds in general. Going from associativity to actual numbers counting curves is quite combinatorially involved, I guess, and gets worse as the classical cohomology ring of your space gets more complicated. A nice worked example is the quadric 3-fold which can be found in Fulton-Pandharipande "Notes on stable maps and quantum cohomology" and more examples are in this paper of Di Francesco-Itzykson.
The key property that $\mathbf{CP}^2$ has which won't necessarily be true more generally is that the recursion formulae only require a finite amount of input to give everything: in the case of $\mathbf{CP}^2$ it suffices to know that there's a unique line through two points to determine all the other numbers. This is because $\mathbf{CP}^2$ is Fano and so as you increase the degree of a curve it moves in a higher and higher dimensional moduli space: the dimension of the moduli space of genus 0 curves in a class $A\in H_2(X;\mathbf{Z})$ with 3 marked points in a $2n$-manifold with first Chern class $c_1$ is
$$2n+2c_1(A)$$
and Fano means $c_1(A)$ increases with the symplectic area of $A$. The Gromov-Witten invariants are obtained by pushing forward the fundamental class of this 3-point moduli space along an evaluation map to $X^3$. Eventually (i.e. for curves of large enough area) the 3-point moduli space becomes so high-dimensional that its fundamental class lives in homological degree larger than the fundamental class of the product $X\times X\times X$ (which is the target of the 3-point evaluation map), therefore the 3-point Gromov-Witten invariants vanish for degree reasons if the area is big enough. By Gromov compactness there are only finitely many moduli spaces of curves with bounded area, so in the Fano case you only ever get finitely many quantum contributions for a given product.
By contrast, for Calabi-Yau 3-folds the expected dimension of a holomorphic sphere is zero no matter what the degree, so you end up having to count infinitely many curves to compute a single quantum product (you get around this by weighting them with Novikov coefficients to encode their areas).
Of course, to answer your specific question, for a completely general algebraic surface you often expect to have no genus 0 curves. For example, a generic K3 surface has no genus 0 curves because you can perturb the complex structure to ensure that there are no $(1,1)$-classes in the rational cohomology. Fano is a good condition for ensuring the existence of genus 0 curves because Mori theory tells us they always exist - a smooth Fano variety is rationally connected (indeed the proof, which I'm told proceeds by passing to a field of characteristic $p$ and then using the Frobenius automorphism of the field to increase the degree of the curve, uses morally the same property that I mentioned above: high degree curves move in high-dimensional moduli spaces).
Note: Kontsevich actually has several proofs of this recursion formula. One of the most beautiful is the one in his paper on toric localisation. That method certainly works more generally than $\mathbf{CP}^2$, e.g. for complete intersections in weighted projective spaces, as he explains there. This method doesn't really have anything to do with associativity, as far as I can see.