Generate new matrix.

We do not do your HomeWork.
HomeWork is not set to test your skills at begging other people to do your work, it is set to help your teacher to check your understanding of the courses you have taken and also the problems you have at applying them.
Any failure of you will help your teacher spot your weaknesses and set remedial actions.
So, give it a try, reread your lessons and start working. If you are stuck on a specific problem, show your code and explain this exact problem, we might help.

Advice: take a sheet of paper and try to do it by hand, your program should use the same procedure.
Nota: I do not even see the need for recursion, a few nested loops can do the trick.