Con recursión lo que te piden es que la función se llame asi misma por que tendrías que hacer algo como esto:
Código C++:
Ver originalint rec(int n){
if (n<1)return 0;
else if (n==1)return 1;
else return 2*rec(n-1)+1;
};
El número en una posición determinada es 2*(número anterior) +1.