# recursion

### edition 39

Researchers tested rhesus monkeys (Ferrigno 2020)

and crows (Liao 2022) on tasks that they say reveal an understanding of recursion. Both studies cited a paper (Gentner 2009), which tested songbirds, for a definition of recursion. Gentner defined it as**an element embedded within another element**. I think that sounds like a definition for

*nesting*but not necessarily recursion.

My understanding of recursion comes from math and software. The definition I’m familiar with is **a function that calls itself**. For example:

```
function myRecursiveFunction (p) {
const x = Math.Random()
const y = p * x
if (y >= 1) { return myRecursiveFunction(y) }
else { return "Done" }
}
const testInput = 99
const testResult = myRecursiveFunction(testInput)
```

If you are familiar with this code you can skip the next two paragraphs.

This javascript function takes one parameter *p*. The constant *x* is assigned a random number between 0 and 1 with a bunch of decimals. The constant *y* is assigned the result of multiplying parameter p times x. If y is greater than or equal to 1, the function is called again passing in y. On each function call the parameter passed in will get smaller because a number times a number less than 1 gets smaller. On the function call where y is less than 1 it will return the text "Done".

You would call this function once and the function would call itself some number of times until it reaches its exit condition. If you don’t write a reachable exit condition the calls could go on forever and crash the program. In more complex examples a function might have side-effects, meaning it mutates information that is stored outside of the function body. A common use-case is having a recursive function for animation frames, which might cycle 60 times a second.

I was surprised to see these papers treat the definition of recursive as less specific than I understood it to be. I looked at “recursive” and “recursion” in a few mainstream dictionaries

, and I think their definitions are more similar to**a function that calls itself**than

**an element within an element**. I don’t think these tests reveal an understanding of recursion, but I could be wrong about the flexibility of the definition.

According to this visual aid from Gentner’s paper, (AB)*n* is not recursive and A*n*B*n* is. A*n*B*n* is the set of strings [ab, aabb, aaabbb, …]) and is generated by “recursive center-embedding”.

They tested if subjects could identify valid A*n*B*n* sequences vs. invalid ones. For songbirds they produced these sequences as sounds, but later experiments with monkeys, toddlers, U.S. adults, native Amazonians, and crows relied on visual symbols. Paired symbols like [ ], ( ), { } were used to generate samples like [ ( { } ) ].

...the crows still had to figure out the center-embedded order where open and closed brackets were paired from the outside in...if the birds only learned that open brackets were at the beginning of the sequence and closed ones were at the end, you would expect an equal proportion of ( { ) } mismatched and correct responses. But...the crows chose more of the latter than the former, even with the more complex sequences of three pairs of brackets.

By the way, crows outperformed rhesus monkeys on these tests.

They mention challenges around proving whether a subject solved tests by understanding recursion or through some other strategy like counting or tracking A-B switches. The group that worked with crows addressed those concerns by coming up with more test samples that subtly violate the A*n*B*n* rule, and suggest that if those violations are recognized, the test subject understands recursion.

I believe there is a problem with the claim because sequences like [ { ( ) } ] are too simple. Subjects can solve this test by understanding symmetry. If you draw a line vertically through the midpoint of the sequence there are two visually opposite halves. Understanding symmetry seems like a lower bar to jump than understanding recursion.

Scientific American published a story about the recent study on crows and got a comment from another researcher who disagreed with the conclusion

:In Rey’s view, the notion of “recursive processing” as a unique form of cognition is in itself flawed. Even in humans, he says, this capacity can most likely be explained through associative learning—which is something he and his colleagues proposed in a 2012 study of baboons

—and to date, there have been no satisfactory explanations of how the ability to recognize and manipulate such sequences would be coded in the human brain. According to Rey, researchers currently fall largely into two camps: one that believes that human language is built on unique capacities such as the ability to understand recursion and another that believes it emerged from much simpler processes such as associative learning.

It’s hard to hold a concept like recursion in your head, and it’s much harder to design a cognitive test for it. To visualize recursion I think about fractals. You could also think about two mirrors facing each other, like in a dressing room or a house of mirrors maze, when you see hundreds of copies of yourself. You can create symmetry with one flat mirror but you need two to get recursion.

I hate to point out a problem and not offer a solution. I need to think more about this subject before offering uninformed takes, but my feeling is that recursion is a higher-level concept than nesting; and nesting is a higher-level concept than symmetry.

Understanding recursion is to understand the function that generates a nested structure. Understanding a nested structure might be proven by being able to deconstruct and then reconstruct something like an onion. Understanding recursion might be proven by being able to deconstruct a nested structure and then reconstruct it according to a slightly different algorithm, like “put these onion layers back together and paint a blue dot on every third layer”.

Stephen Ferrigno et al., Harvard University. *Recursive sequence generation in monkeys, children, U.S. adults, and native Amazonians.* 2020 (link)

Timothy Gentner et al., University of Chicago. *Recursive syntactic pattern learning by songbirds*. 2009 (link)

The New Oxford American Dictionary, Merriam-Webster, Collins, and Wikipedia