🛑 Spoilers Ahead: This topic doesn't appear on the Techtonica curriculum until week 7. It is only mentioned on this post because someone said to me "recursion is hard". So, if you know what recursion is and also think it's hard, read on, otherwise you might want to wait until the topic is formally introduced.

If you're still with me, let's see... what's up with this recursion thing:

function factorial(n) {  
  if (n === 0) return 1; // base case
  return n * factorial(n - 1);
}

One defines a base case, a recursive step, and done! Easy enough, right? Not quite, I think. Recursion is often taught as an alternative to looping in the context of an imperative programming language as a way to simplify the code. Let's see what the factorial() function looks like written in a more imperative way:

function factorial(n) {
  let result = 1;
  for (let i = 1; i <= n; i++) {
    result *= i;
  }
  return result;
}

So, it's not much worse in terms of style and if you're already comfortable with for loops and variables, it may feel much more comfortable. So, if you are still curious about recursion, let me tell you the story of recursion the way I learned it when I was in college...

Disclaimer Please note that in the preceding examples, in an effort to keep the code simple, I omitted checking the function's input parameters. In your code you should check your input params, in this case you could have used something like:

if (!Number.isInteger(n) || n < 0) { // 
    throw new Error('Invalid argument: "n" must be a non-negative integer.');
}

Ok, on with the storytelling: in a land far, far away... in a forgotten time (?) there was a programming language known as Haskell.

Haskell did not have loops of any kind, nor it had any variables (in the traditional sense) or instructions/statements. But, you say, how are you supposed to program without loops, variables and instructions?? (I can hear the outrage).

The answer is: functions. Haskell gives you:

• Functions.
• Constants (immutable variables, i.e. once you do x = 5, you can't assign x any other value).
• A few other things we're not going to get into here.

So, if all you have are functions, then recursion all of the sudden becomes your best friend! Let's look at factorial() in Haskell. The syntax will look a bit weird, but worry not, it's actually pretty easy to understand:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

The way to read this in plain English is:

Line 1: "There is a function factorial which takes an Integer as its only parameter and returns another Integer". Line 2: "When factorial 0 gets called somewhere, return 1". Line 3: "When factorial n gets called, take n, multiply it by the result of factorial(n-1) and return that."

If you think this is more similar to a mathematical definition than a computer program, you are correct! Haskell is what is known as a declarative programming language (and, in particular, a functional programming language) . In this world you describe the relationships between the operations and not the control flow. The language itself will figure out how to produce the desired result.

You may still be wondering how this detour into the declarative programming rabbit hole will help you understand recursion better. In my humble opinion, for recursion to make sense you have to forget that you are in the imperative paradigm and imagine you are in the declarative realm, where all operations are defined as functions of other operations.

In every recursive function you need a base case, which is the basic fact or state from which all other cases can be derived, and we usually write that first, probably to avoid forgetting about it (we forget, we get infinite recursion and bad things happen).

This type of programming generally shines when dealing with repetitive patterns or structures, for example lists and trees.

Recursion has all sorts of problems when used in imperative languages, but it is usually taught that way because of their popularity, and because people don't have the time to learn an entirely new programming language.

However, many popular programming languages are a confused mess of features (ahem, JavaScript...) taken from other languages, for example:

[1, 2, 3].map(x => x * 2);

written in Haskell...

map (\x -> 2 * x) [1, 2, 3]

See any similarities?

In fact, I believe a good chunk of the success of JavaScript is due to their adoption of functional programming features, but I digress.

To come back to my earlier point, learning about recursion using an imperative language feels like doing it the hard way, and even though it may be quicker in the short term, the long-term learning suffers. After spending some time with a purely functional language like Haskell you begin to internalize that, in writing code this way, you are describing the behavior of data structures in a very elegant way, but letting go of the illusion of control provided by fors, ifs, etc. can be really hard at the beginning.

I will leave this topic here for now, and maybe pick it back up if folks are interested in it. There is also a fascinating rabbit hole to explore in how recursion works under the hood and it's effects on memory management.

Making a choice between imperative and declarative programming, is also a choice of coding style and specifically of code structure, which leads us to the next topic...