A recursive image from Wikipedia

It's the weekend and I didn't have much free time today so I'm covering recursion.

Recursion is an important topic in programming that often gets looked over because oftentimes it's used in self-evaluating algorithms. But before I go into Opinionland, I'm going to define what recursion is.

What is recursion?

I really like the Wikipedia definition of recursion even if it's sort of confusing:

Recursion occurs when the definition of a concept or process depends on a simpler version of itself.

Ok so what does that mean? To me, it made sense once I looked at an algorithm that uses recursion, inside merge sort. But let's define things that make up a recursion so that it's a bit easier to understand.

Recursion contains:

Base case: think of this as a step that the function has to take or else it will have not-so-fun consequences (more on this soon).

Recursive step: this step is one that seemingly just calls itself based on a condition that doesn't send the function into another call to itself.

Here's some pseudocode that might explain this too:

function recursiveFunction(parameters):
  if baseCase is true:
    return something
    someValue = doSomething(parameter)

    return recursiveFunction(someValue)

Let's take this line by line:

  1. We define a function called recursiveFunction that will take parameters as the argument when called.
  2. A – We check the base case and if the conditional checks to be true, we return something. Here, something can be some calculated value or just the same value passed into it.
    B – If the base case is not true, then we do the following:
  3. Calculate some value from doSomething which should do something like modify the value, get some resulting thing, because this will become useful next.
  4. We run the recursive function again and just pass the value we just got from doSomething.

If you didn't cause any issues that would never hit the base case, you should be good to go. If you didn't catch your base case, then your function will run over and over forever–or until you kill it.

That seems to make sense to me. Now, I'm going to log off and test this tomorrow.