[retrac]

Language has an inherently recursive structure: I saw the man who saw the man who saw the man who saw the man who saw the man who... While our brains have practical limits to how deeply such things can actually be nested, language has a recursive tree-like aspect to it.

[umanwizard]

Yes, but “language is fundamentally recursive” doesn’t mean the same thing as “recursion is fundamentally linguistic”. Language is just one example of a recursive structure.

[a4isms]

I am also unsure whether recursion is fundamentally linguistic, but I thought that “language remains the easiest demonstration of recursion in our daily lives” to be useful. If I ever write another essay about recursion, I'll now consider starting with a linguistic example before diving into recursive functions or data structures.

[Jensson]

Language has nothing that corresponds to a recursive function, so that is a bad example. You can write a sentence that could correspond to a call to a recursive function, but its not the same thing as a recursive function.

If recursion was just writing the function 10 times like you did in language then people wouldn't struggle with it.

[deeThrow94]

Recursive functions are just a subset of all possibly recursive concepts. In the case of human spoken language, the recursion exists in our characterization of the grammar. You could just as easily frame this in "iterative" terms just like you can make any recursive function iterative, but that's less convenient for analysis.

So in this case, "recursive function" would be "clause" or something like that; I'm no linguist. But clauses can embed clauses which can embed further clauses, etc.

I think your usage of recursive functions is just high-level logic—you're describing an inductive proof. We also frame a lot of our social games as recursive processes. But these are conscious processes that we can evaluate consciously; the recursion in spoken language is largely unconscious and very shallow.

[Jensson]

> In the case of human spoken language, the recursion exists in our characterization of the grammar

But people are constructing sentences, not grammars. When you construct a grammar you can add a recursive part to it, that is true, just like in a programming language, but constructing grammars is not what people mean with language skills.

A sentence can't be recursive since languages in themselves has no concept of applying a concept, for that you need an interpretation of the language references. For example, you can have a recursive function written in a programming language that doesn't have a recursive grammar, the concepts are different things.

[deeThrow94]

There are two ways that recursion intersects with language that are relevant here:

1. Our spoken and especially written grammar is recursive. We do handle this unconsciously. This is not related to our ability to reason about recursion at a high level, and recursive grammars are not necessary to do so. This is not a skill in the normal sense and we have only (very) limited ability to improve our capacity to interpret deeply nested grammars. However, this is still a useful illustration of what recursion IS, which is why I brought it up.

2. Language also introduces the ability to semantically reason about recursiveness. This is still a linguistic thing—you need a symbol and relations among symbols in order for recursion to be meaningful—but this is a skill and is likely very related to linguistic skill. This is the part that really helps you to program: ultimately, you're just reasoning about symbols and looking for incoherency.

[deeThrow94]

Can you come up with some conception of recursion that doesn't involve symbols referring to themselves, directly or indirectly? Ie what is left of recursion when you remove the linguistic component?

[karmakaze]

Yes. But it's in my mind, I can't write it down for you.