Is recursion only something we see in the world, or is it something in the world itself?
This is a question we should be pouring over, and puzzling about. But instead I see people either in full thrall of some kind of pan-recursionism, or else denying that it could exist anywhere.
If we're ever able to discover a reasonable answer to this question, we may not be able to remember it for long enough to make use of it. Recursion is very appealing, and the reason seems to relate to the mechanism behind the human language faculty, something we're all born with.
Human language is some kind of cyclic composition faculty, which interacts with and recruits from the rest of the brain in surprising ways. We see superficial externalized aspects of this cyclicity in written and spoken language, such as 'phrases within phrases ad infinitum'.
If the language faculty, at its core, is a kind of cyclic composition engine, it's no wonder that we find recursion so seductive. We have a "recursion meter", if you will, in a prominent place in our cognition. We can sense when something could be perceived 'recursively'.
It also seems to be deeply integrated with our desire for simple, comprehensible symbolic theories about the world, probably responsible for the phenomenon Charles Sanders Peirce called abductive reasoning. We look for self-similar patterns embedded within each other. The faculty forces us to look for simple theories that enlighten us, and hence explain something to us, about hopelessly complex-looking phenomena -- Newton's laws of motion are a classic example. Although the modern mathematical study of recursion is a 20th-century phenomenon, it's only a refined version of something that clearly impacted human efforts long before. Which, again, is not surprising, if it's part of the innate language faculty.
All of this doesn't mean, though, that recursion is somehow the 'best tool' for people, in all, or even any, situations. There's a reason for that. It's known as reality.
Take programming languages. From LISP to Haskell, languages that encourage the compression of computational representation into recurrence relations are easy to define, sometimes inspiring to use, but they relate poorly to the non-logical side of programming.
By the 'non-logical side of programming', a phrase that will surprise many programmers, I mean nearly everything. That will surprise most programmers.
Almost nothing in the act of programming involves 'logic', in the sense of 'rule-based symbol manipulation'. But it does involve logic in the older sense of 'good thinking', a sense that is much closer to the natural sciences, where there is very little presumption that we have somehow magically turned the world into symbols. There is far less confusion, within the natural sciences, between "the map" (formal notation, math, idealization etc.) and "the territory" (the world outside our minds, which we've a very limited, and specific, ability to perceive.)
Think of any symbol in any programming language -- let's take the word 'if' in a formal conditional construct. What does the 'if' mean? We can construct a machine that satisfies us with its conditional-like behavior, which we can call 'if' -- but 'if', the word itself, has a mind-internal meaning. There's no way to "teach" a machine what we understand by the word 'if'. We can only inject into a machine a behavior that people will typically perceive as 'conditional', if they know it was constructed by another human being.
So even at the most elemental level, symbols mean nothing without people. We can of course force machines to react to people-assigned representations of symbols. But the satisfying reactions, the assignments, the low-level interpretation, the high-level interpretation, the user's feelings -- none of these are definable as a formal rule-based system of symbolic logic. The symbolic logic is only a shorthand, only a set of partially-ordered artifacts, little more than markings on paper, constructed by and awaiting the massively complex use and expectations of the human cognitive faculties.
Which is why recursion is so 'dangerous'. It's simply an appealing feature of symbolic logic, which appeals to a very specific aspect of a particular faculty in our minds. But we don't live in some biological cyclic compositor. We live in a complex world that we do not even slightly understand, which our complex brains impose complex interpretations upon. And the abilities of these complex brains are not only understood poorly -- that would be excusable -- but they are actively misunderstood by almost all computer scientists, who regularly reside within fallacies that were understood millennia ago.
These misunderstandings exist because computing began as an engineering discipline: automating production, and building tabulators and calculators. Within the computing discipline, people create and use formal systems. But I believe the limits to these formal systems have been reached, and were reached decades ago, and will remain in the dark ages, until a broader study of the biology of programmers and users, the role of people in the systems they create and use, is studied from a natural science perspective -- instead of from a seat-of-the-pants pragmatism, exalting "whatever works", "whatever's profitable", and "whatever gets the product out the door".
… a few more points.
If a cyclic composition mechanism exists in the mind, in whatever form, that would mean it exists in nature. So, in some sense, a machine of some kind that exhibits perception and generation of recurrent relations, is the result of natural physical laws and our human genetic endowment. In some sense, it could be a very simple machine, that is 'optimal' in some sense: the next cycle can proceed by ignoring all but the 'most important result ' of the previous cyclical work. What's being optimized is not that clear. What the mechanism is, is yet unknown, so we cannot begin to know how this 'simple' set-construction mechanism appeared.
As a candidate for symbolic computational recursion in nature, cell self-reproduction is often presented. But it's not clear yet if the 'genetic component' (genes as narrowly defined by molecular biologists) is the decisive one in the recurrent relation, or whether these genetic 'symbols' (which is only a 'symbol' by a rather extreme metaphor) merely piggy-back on biophysical reproductive behavior, such as the vesicles that Pier Luigi Luisi has pointed towards in abiogenesis research.
Even further from the mark, and further towards our recursive 'perceptual trap', if that's not putting it too strongly, are fractals.
Fractals in nature, when most compelling, mostly look like a gradient of energy, dissipating through a medium that reacts similarly at a few different scales. A bullet-hole through glass looks like this: lots of breaks close to the impact, with geometrically similar but larger and fewer breaks as the energy dissipates.
Even in those cases, the recursive characterization is part of human cognition, not nature. That's ok, if we understand that it's only for calculation purposes.
As physical idealizations, fractals fall apart rather quickly. A tree is a good example. Leaves do not vary in size after they've reached maturity. The behavior of any organism involves a great many factors, which change radically at different scales, and cannot even be superficially characterized as fractal. Fractals are a phantom of our mental recursive trap, and in the natural sciences, they, and recursion generally, need to be recognized as a kind of potent fantasy.