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.
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:
if baseCase is true:
someValue = doSomething(parameter)
Let's take this line by line:
- We define a function called
recursiveFunctionthat will take
parametersas the argument when called.
- A – We check the base case and if the conditional checks to be true, we return
somethingcan 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:
- Calculate some value from
doSomethingwhich should do something like modify the value, get some resulting thing, because this will become useful next.
- We run the recursive function again and just pass the value we just got from
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.