Lara Schenck

When do you need to understand recursion?

During my years as a primarily UI programmer, I don’t think I explicitly encountered recursion until I had to study for an algorithms interview, several years into my programming career! That said, recursion is cool and worth understanding…even if you are forced to learn it for an interview.

Recursion is one of those computer science concepts you’ve probably already encountered but may not have realized it – for example, array manipulation methods like map, filter, and reduce in JavaScript are recursive. If you’ve had a tough time understanding those (I did), learning more about recursion might help!

An analogy: Recursion in a template

We usually hear about recursion in the context of functions, but let’s look a recursion-like instance in a template. In its most distilled form, recursion is a function calling itself – so, is a template including itself as a form of recursion? Maybe and maybe not, but the same concepts apply and it can be a useful analogy.

Here is an example of this from our design system at work. There’s a lot of syntax here – for any template / design systems enthusiasts out there, it might be interesting 🤓…and if it’s confusing, “stare at it until it makes sense” (some of my favorite advice from Zero Bugs and Program Faster by Kate Thompson):

{# @larva/modules/list/list.twig #}

<{{ list_type_name }}l class="list // {{ list_classes }}">
	{% for item in list_items %}
		<li class="list__item // {{ list_item_classes }}">
			{% if item['list_items'] %}

				{# The template recursively includes itself #}
				{% include "@larva/modules/list/list.twig" with item %}
			{% else %}
				{{ item['list_item_markup'] }}
			{% endif %}
		</li>
	{% endfor %}
</{{ list_type_name }}l>

The data sent to this template looks like:

{
	list_classes: 'a-font-body-m',
	list_markup: 'Outermost list.',
	list_type_name: 'u',
	list_items: [ 
		{
			list_item_markup: 'Item one', 
		},
		{
			list_item_markup: 'Item two', 
		},
		{
			list_classes: 'a-font-body-m',
			list_markup: 'Nested list',
			list_type_name: 'u',
			list_item_classes: '',
			list_items: [
				{
					list_item_markup: 'Nested list item', 
				},
		}
	],
}

Recursion in a function

Now, let’s look at an example of a function calling itself:

function recursiveCount( count ) {
    return recursiveCount( count + 1 );
}

Unlike templates, recursive functions need a “base case” that will tell them when to terminate, otherwise the function will run forever and the system will run out of memory. Here is the above function, with a base case:

function recursiveCount( count ) {

    // The base case
    if ( 100 === count ) {
         return 'Counted to 100';
    }

    return recursiveCount( count + 1 );
}

In the template example, we do not need an explicit base case because the amount of data is implicitly a base case. We could call it a declarative sort of base case that we say what – in the form of how much data – not how, as in the conditional like above which would be imperative.

Anyway, that’s barely scratching the surface of recursion, but maybe it’s a small example that will help. I needed to hear several different explanations of recursion and allow a lot of time to go by for my understanding to really solidify. Learning a bit of programming in a functional language (Standard ML in this course) helped the most.

What programming concepts took you a while to really understand?

A future post…examples of recursion in CSS!

The box layout algorithm, for one, is a great example and there are surely many more. I haven’t done any digging into browser code for quite a while…the time may come again soon!