Recursion is one of those computer science topics that, once you first come across your head, your thinking… is this really necessary? Why do I really need to learn this, or is it mandatory? I usually lean towards the iterative approach. But after deep diving into one of my most frustrating topics, I am more comfortable working with recursion. I use this article to explain my mindset when approaching recursion, as this is my second time coming across this topic.
What is Recursion?
In programming terms, recursion is defined as a pattern useful in situations when a task can be naturally split into several functions of the same kind but simpler. It derives from the divide and conquer algorithm design paradigm. Essentially it is a function that calls itself.
My personal definition of recursion helps me get to the root- the process of breaking down a problem into two different paths. One path allows for exiting the loop since it is a function that calls itself within itself. And the other path provides the opportunity for the function to call itself.
The Process
There are actual steps to take that can be factored into one’s pseudocode.
The first two recursion steps define the base of recursion and recursive steps. The base is what allows the loop to stop once the condition is met. The simplest form of recursion enables the function to end.
The Recursive steps are known as where the actual processing takes place. In other words, the function will call itself. Still, decreasing its parameter value with each loop is usually necessary.
The Challenge
Let’s take an example and work through the problem. First, the iterative, and then we’ll assume that same function and convert it to a recursive one.
Write a function that will:
- take a number as input
- return the sum of all numbers from 1 up to the number passed in
Example:
sumTo(3)
The Iterative Function
First, I like to be completely clear about the goal I am to achieve, which is to add the number in succession from 1 to the input/parameter value.
Now for the code in plain English(pseudocode)
- Create a variable that will hold the sum
a. name the variable sum
b. initiate it at 1
- Create a variable that will act as the counter
a. initiate it at 0
- If the counter is less than OR equal to the parameter/input value
a. add the value in the sum and the value in the counter
b. increase the counter by 1
- If the counter passes the input parameter
a. return the result which in this case will be the variable sum
The Iterative Code
function sumNumbers(n){
let sum = 0;
for(let i = 0; i <= n; i++) {
sum = sum + i;
}
return sum;
}
The Recursive Function
Same goal but a different approach.
Once again, there are two steps to keep in mind to start the pseudocode. The base and the recursive steps.
For the recursive steps, it's great to think of it as the way of finding out how the input value can reach the terms/conditions of the exit value.
The Pseudocode
- Create the base of recursion
a. If the input is equal to 0 return the input value
- Create the Recursive steps
a. add the input value to the recursive function with the parameter subtracted by 1
NOTE: Step 2a allows for "divide and conquer" to occur and allows the algorithm to reach the base to exit the loop
The Recursive Code
function sumNumberRecursive(n){
if(n == 0) return n;
return n + sumRangeRecursive(n - 1);
};
Why Recursion?
Recursive can be hard to grasp. But once you understand the flow of what's going on and what's needed, the benefits are clear.
Cleaner Code
It is always great when the code you write is concisely readable by someone other than yourself. Makes working in teams fantastic.
Efficiency
Some code can take up some time and memory on your computer. Recursion can solve that problem by speeding it up. Sometimes it can take longer, but it is up to the coder to decide when to use recursion and iterative algorithms.
Wrapping Up
Some topics are great, and some are not so fun. But if you take it to step by step, divide and conquer, a little will always go a long way. Hope this article was able to clear things up for anybody struggling with recursion. And as always, any feedback/requests and questions are welcome.
