Is this what you're looking for?

In[1]:= NestList[f[1 + #] &, 0, 4] Out[1]= {0, f[1], f[1 + f[1]], f[1 + f[1 + f[1]]], f[1 + f[1 + f[1 + f[1]]]]} 

This may not be ideal or the most elegant, but perhaps it will work or help.

Define (note that int can be whatever range you want):

In[3]:= a[0] = 0; int = Range[4]; 

Create a list of symbols for your LHS:

In[3]:= lhs = a[#] & /@ int Out[3]= {a[1], a[2], a[3], a[4]} 

This gives us your RHS's, primarily just mapping a expr /. rule expression across the iterators {1,2,3,4}:

In[4]:= vals = (Sqrt[s[# - 1]^2 + s[# - 1] + 1] /. s[# - 1] -> FoldList[#1 + a[#2] &, int - 1][[#]]) & /@ int Out[4]= {1, Sqrt[1 + a[1] + a[1]^2], Sqrt[  1 + a[1] + a[2] + (a[1] + a[2])^2], Sqrt[  1 + a[1] + a[2] + a[3] + (a[1] + a[2] + a[3])^2]} 

And you can thread Set across them to get your end result:

In[5]:= Thread@Set[Evaluate[lhs], vals] Out[5]= {1, Sqrt[3], Sqrt[2 + Sqrt[3] + (1 + Sqrt[3])^2], Sqrt[ 2 + Sqrt[3] + Sqrt[ 2 + Sqrt[3] + (1 + Sqrt[3])^2] + (1 + Sqrt[3] + Sqrt[ 2 + Sqrt[3] + (1 + Sqrt[3])^2])^2]} 

To verify this...

In[6]:= {a[1], a[2], a[3], a[4]}  Out[6]= {1, Sqrt[3], Sqrt[2 + Sqrt[3] + (1 + Sqrt[3])^2], Sqrt[ 2 + Sqrt[3] + Sqrt[ 2 + Sqrt[3] + (1 + Sqrt[3])^2] + (1 + Sqrt[3] + Sqrt[ 2 + Sqrt[3] + (1 + Sqrt[3])^2])^2]} 

Like I said, you can let int be as high as you want to define as many values of a[n] are necessary. This isn't recursive, but it would work. Hoping someone can provide a better solution :)