Creo que dejas varias dudas en tu mensaje.
Normalmente una matriz es bidimensional (con n filas y m columnas) pero cuando la matriz es cuadrada, en vez de decir que tiene n filas y n columnas (o como se denota normalmente: nxn), se dice que es de orden n.
Ahora bien, en tu caso no estoy seguro de que el parámetro n se refiera a la dimensión o al orden.

Es mejor que pongas un ejemplo concreto, como por ejemplo (predicando con el ejemplo ):
"Necesito implementar una función que reciba como parámetro el orden de la matriz <crearMatrizRecursiva(int orden)> y genere una matriz de 2 dimensiones y de tamaño (orden x orden)"

Para ese supuesto que he puesto primero imagina cómo lo harías de manera iterativa:
(No sé en que lenguaje lo necesitas así que haré el ejemplo en C++... Hay que procurar ser lo más concreto posible cuando se solicita ayuda)

int** generarMatriz(int orden){
    int **matriz = new int* [orden];
    for(size_t i = 0; i < orden; ++i)
        matriz[i] = new int [orden];
    return matriz;
} 

La recursividad normalmente lo que hace es eliminar un bloque iterativo y convertirlo en una sentencia condicional. Además alguno de los parámetros tiene que ir cambiando para en algún momento llegar al caso base que es el que termina con las llamadas recursivas.
Como en la función anterior sólo tenemos un bloque iterativo, será la parte que implementaremos de manera recursiva. Existen diferentes formas de hacerlo, una de ellas es esta:

int** generarMatriz(int orden){
    int **matriz = new int* [orden];
    generarMatrizRecursiva(matriz, orden-1, orden);
    return matriz;
}
 
void generarMatrizRecursiva(int **matriz, int filaActual, int orden){
    if(filaActual >= 0){
        matriz[filaActual] = new int [orden];
        generarMatrizRecursiva(matriz, filaActual-1, orden);
    }
} 

Esta versión es muy simple pero creo que es la mejor para que entiendas cómo funciona la recursividad. Si quieres añadirle un poco más de gracia, te recomiendo cambiar el orden de las instrucciones y comprobar si puedes explicar su funcionamiento ahora. Pero eso ya es cosa tuya...

void generarMatrizRecursiva(int **matriz, int filaActual, int orden){
    if(filaActual >= 0){
        generarMatrizRecursiva(matriz, filaActual-1, orden);
        matriz[filaActual] = new int [orden];
    }
} 

Y no olvides liberar toda esa memoria antes de terminar el programa...

PD: No te acostumbres a recibir los ejercicios hechos. Esta ha sido una excepción por la Navidad   

Muchas gracias a los dos, lo lamento por no explicar bien mi problema, pense que seria mas facil de explicar pero basicamente lo que me piden es a partir de una matriz: typedef float matriz[10][10], crear una funcion mendelbrot(c,n,m) que cree una matriz recursivamente recibiendo como orden n^2, osea que tiene que ser del orden 2x2 3x3 y asi, el problema es que recibe una matriz y no la crea como me lo indicaron anteriormente, y eso es lo que me complica. muchas gracias a ambos por sus respuestas, no he podido encontrar algo acerca de esto y me ayudan muchisimo.