# Recursive definition of nested functions

This is probably very easy, but I cannot figure out a way to define a function like: $$g_h = ( 1 + f_1(1+f_2(1+f_3(.. (1 + f_h)))))$$

-
Look up Fold[]. – J. M. Mar 8 at 15:39
@J.M. "easily found in the documentation" ?? – Mr.Wizard Mar 8 at 15:40
@Mr. Wizard, if you put the word "fold" in somewhere, sure… otherwise no. ;) – J. M. Mar 8 at 15:41

Fold should work for you:

Fold[1 + #2[#1] &, x, Reverse @ {f1, f2, f3, f4}]
1 + f1[1 + f2[1 + f3[1 + f4[x]]]]
-
I was about to submit this when your answer showed up. This gives OP's more exactly I think: g[h_] := Fold[1 + Subscript[f, #2][#1] &, 1 + Subscript[f, h], Reverse@Range@(h - 1)] – JasonB Mar 8 at 15:41
@JasonB If the OP wants to generate this expression for typesetting that will help. If writing a program I would recommend avoiding subscripts. – Mr.Wizard Mar 8 at 15:42
People like their subscripts, who are we to fight? :-P – JasonB Mar 8 at 15:46
@Mr-Wizard, can you point me to a post on here where it clearly shows the pitfalls of using Subscript indiscriminately, in a common situation? I don't use it myself, but it was years before I figured out that f[1] was the right substitute for $f_1$. Until then, I was doing ToExpression["f"<>IntegerString[1]] in my loops, which is cumbersome. – JasonB Mar 8 at 15:53
@JasonB point #3 in (18395) is the first thing that comes to mind. Perhaps there is more. I simply know that many experienced users have cautioned against this, and early in the process of learning Mathematica I had a number of problems which I later traced to the use of subscripts. As a result I reserve Subscript almost entirely for formatting. – Mr.Wizard Mar 8 at 15:56

So the way to get exactly what is written is

g[h_] := Fold[1 + Subscript[f, #2][#1] &, 1 + Subscript[f, h], Reverse@Range@(h - 1)]

so that

g[5]

gives

But as is pointed out all the time here, you should avoid subscripts. Anytime you want to use $f_i$, you should use f[i] instead. So in this case what you need is

g[h_] :=
Fold[1 + f[#2][#1] &, 1 + f[h], Reverse@Range@(h - 1)]
g[5]
(* 1 + f[1][1 + f[2][1 + f[3][1 + f[4][1 + f[5]]]]] *)

Less readable, but now you don't have to worry about what a DownValue of Subscript is.

-

I know that "mutable states" are nearly taboo on this site, but Nest also can be used:

i = 5; Nest[1 + Subscript[f, i--] @ # &, "...", i]

Result:

Edit

Also for fun of it, a couple more freak options:

Fold[1 + Symbol["f" <> ToString @ #2][#1] &, x, Range[5, 1, -1]]

and

Fold[1 + #2[#1] &, x, Table[Symbol["f" <> ToString @ i], {i, 5, 1, -1}]]

both produce:

1 + f1[1 + f2[1 + f3[1 + f4[1 + f5[x]]]]]

-
Mind you that, in general, state is avoided for important reasons! – Aisamu Mar 8 at 21:21
@Aisamu, sometimes it is not reasonable to avoid them. – garej Mar 9 at 4:50