Yes, that’s correct. I’d view “f((((...) + 1) + 1) + 1)” as an equivalent way of writing it as a string (along with the definition of f as f(n) = f(n + 1)). ”...(((((...) + 1) + 1) + 1) + 1)...” just emphasizes that the expression tree does not have a root—it goes to infinity in both directions. By contrast, the expression tree for f(n) = f(n) + 1 does have a root; it would expand to (((((...) + 1) + 1) + 1) + 1).
Just to make sure I understand, the first few expansions of the second one are:
f(n)
f(n+1)
f((n+1) + 1)
f(((n+1) + 1) + 1)
f((((n+1) + 1) + 1) + 1)
Is that right? If so, wouldn’t the infinite expansion look like f((((...) + 1) + 1) + 1) instead of what you wrote?
Yes, that’s correct. I’d view “f((((...) + 1) + 1) + 1)” as an equivalent way of writing it as a string (along with the definition of f as f(n) = f(n + 1)). ”...(((((...) + 1) + 1) + 1) + 1)...” just emphasizes that the expression tree does not have a root—it goes to infinity in both directions. By contrast, the expression tree for f(n) = f(n) + 1 does have a root; it would expand to (((((...) + 1) + 1) + 1) + 1).
Does that make sense?
I think that makes sense, thanks.