Twoim pojedynczym działaniem jest n*n-1, a nie n. Idąc tym tokiem rozumowania twój return powinien wyglądać tak:
n* n-1 + rekurencja(n-1)
Napisałam tę funkcję w Pythonie, to sobie zobaczysz. I spokojnie, wiem, że to nie Python, ale algorytm jest ten sam. Masz do analizy.
def rek(n):
if(n==0):
return 1
return n * (n-1) + rek(n-1)
Pozdrawiam