Given a shape, return all triangles that can be formed
No, it doesn't mean \$O(n!)\$ complexity.  The \$(n-r)\$ in the denominator cancels most of the terms in the numerator.  For choosing three points to make a triangle, \$r\$ = 3, and so your actual expression is \$\frac{(n)(n-1)(n-2)}{3!}\$ => \$\frac{(n^3-3n^2+2n)}{3!}\$ => \$O(n^3)\$.

So you should expect \$O(n^3)\$ time, and \$O(3*n^3)\$ => \$O(n^3)\$ space.

Next thought - if you are going to be working with triangles, you need to know where the points are (so that you can check whether or not the points are co-linear).  What your code currently does is seek out every 3-tuple combination of vertices; so you are (possibly) missing part of the problem.

That said, breaking the triangle problem into two distinct pieces is a good idea; because you do need to enumerate the vertices anyway, and treating them as ordered tuples gives you a good way to avoid extra work.

But trying to enumerate the tuples using recursion... that's a bad idea.  Better would be to simply enumerate the combinations using squashed ordering.  Thomas Andrews has a nice illustration of that technique on a more complicated problem.