exupero's blog

# Song recursion

There are a couple children's songs I've used as examples to help explain tail-call recursion: "The Song that Never Ends" and "My Name is Yon Yonson". Often people think of these songs as loops, since when singers reach the end of the only verse they start again at the beginning, but in both cases the song is actually recursing into itself.

In the "Song that Never Ends", the last line proposes to explain why the song never ends, then uses its own lyrics as that explanation:

This is the song that never ends.
Yes, it goes on and on, my friend.
Some people started singing it not knowing what it was,
and they'll continue singing it forever just because
this is the song that never ends...

In "My Name is Yon Yonson", the song is styled as a biography, which the singer gives when introducing himself to people in the biography:

My name is Yon Yonson.
I come from Wisconsin.
I work in the lumber mill there.
When I walk down the street,
all the people I meet
say "Hello, what's your name?" and I say,
"My name is Yon Yonson...

Since the last line in both songs sets up the recursion, I think of them as examples of tail-call recursion, which in programming language implementations can be optimized into non-recursive loops.

That's can be a helpful illustration for explaining tail-call optimization, but the caveat is that the songs might be recursing before the tail position. In that case, they're examples of regular recursion. Conceivably, there could be verses after the one verse we know, but singing never reaches them because the songs first fall into infinite recursion from which they never terminate.

Even without extra verses we can see that "My Name is Yon Yonson" recurses before the tail position. Grammatical rules dictate that the nested biography, being used in conversion, should be placed within quotes, meaning the end of the song should close with a double quote mark. However, due to the infinite recursion, we never see that closing quote mark.

If you know of other songs that recurse, feel free to email me.