How can I write this with Nest or Fold?

NestList[f[## & @@ # + #] &, f[1], 3] 

{ f[1], f[1 + f[1]], f[1 + f[1] + f[1 + f[1]]], f[1 + f[1] + f[1 + f[1]] + f[1 + f[1] + f[1 + f[1]]]] } 

alternatively (but we have to start with f[1+f[1]]:

NestList[Insert[#, #, {1, -1}] &, f[1 + f[1]], 2] 

{ f[1 + f[1]], f[1 + f[1] + 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 :)