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]]]]
}

NestList[# + Sqrt[#^2 + # + 1] &, 0, 4] // Differences // Column

enter image description here


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 :)