Writing Algorithms using recursive solutions

In computer science, an algorithm is a set of steps for a computer program to accomplish a task. Finding a good algorithm and knowing how to apply it will allow you to write interesting programs and automate your workflow. There are often many different ways to accomplish a given task. Each algorithm has its own advantages and disadvantages in different situations, e.g. some can be used efficiently with large data volumes when others will work better with small amount.
This publication is an introduction to some of the algorithms available and how they work. A technique called recursion is used together with JavaScript for coding the algorithms.
Recursion is a technique for iterating over an operation by having a function calling itself repeatedly until it arrives at a result. Most loops can be rewritten in a recursive style, however, while JavaScript’s functional coding style does support recursive functions, we need to be aware that most JavaScript compilers are not optimised to support them safely.
Linear Search
A linear search is the most basic search algorithm you can have. It sequentially moves through your collection looking for a matching value.
Implementation:
const linerSearch = (array, target, currIndex = 0)=> {
if(array[currIndex] === target){
return currIndex;
}
else if(array.length - 1 === currIndex){
return null;
}
return linerSearch(array, target, currIndex + 1);
}- The function
linearSearch()takes three argumentsarray— the values we want to search throughtarget— the target value we are searching forcurrIndex— current index of the array — starting from 0 by default - We check if the current value in the array is matching our target.
If so, the index of the value is returned. - Next, we check if iterated through the whole array. If so, we did not find our target and we return null.
- If the values do not match we call the function again by passing the same
array,targetand increment the index by 1 to check for the next value in thearray.
Example output with target = 6
const numbers = [11,3,6,8,1,12,4,2,5,7,9,5];
linerSearch(numbers, 6);Index: 2, Target: 6
Euclidean Algorithm
The Euclidean algorithm is a technique for quickly finding the Greatest Common Divisor (GCD) of two integers. Discovered by Euclid in the mid-4th century BC, it’s referred to as the world’s oldest algorithm.
The algorithm for finding GCD(firstNo, secondNo) is as follows:
- If firstNo = 0 then GCD = secondNo, and we can stop
- If secondNo = 0 then GCD = firstNo, and we can stop
- Find the remainder of the larger number divided by the smaller number (Modulus operation)
- Next, find the remainder of the previous divisor and previous remainder
- We repeat the same operation until our remainder is equal to 0
- When the remainder is 0, the divisor of the last operation is found to be the greatest common divisor
Implementation of the Euclidean algorithm
const euclidianAlgorithm = (firstNo, secondNo) => {
if(firstNo === 0){
return secondNo;
}
else if(secondNo === 0){
return firstNo;
}
else if(firstNo < secondNo){
const tempNo = firstNo;
firstNo = secondNo;
secondNo = tempNo;
}
return findRemainderOfDivision(firstNo, secondNo);
}- First, we check if the first number is equal 0. If so, we return the second number as the GCD.
- Second. we check if the second number is equal to 0. If so, we return the first number as the GCD.
- Then, we make sure that our dividend will always be the larger number of both.
- After making sure that the numbers are all good, we are calling the recursive function again for finding the remainder of the division of the two numbers. The function is as follows:
const findRemainderOfDivision = (firstNo, secondNo) => {
const remainder = firstNo % secondNo;
console.log(`${firstNo} mod ${secondNo} = ${remainder}`)
if(remainder === 0){
return secondNo;
}
return findRemainderOfDivision(secondNo, remainder);
}- We are using the Modulus operator to return the remainder left over from the division of both numbers.
- We use
console.log()to display each operation’s result. - If the remainder of both numbers is not zero, we are calling the
findRemainderOfDivision()function again, but using the second number as our first number and the remainder as the second number. - Once the remainder is equal to 0, we are returning the divisor of the last operation which is found to be the greatest common divisor.
Example output with firstNo = 1428 and secondNo = 222
euclidianAlgorithm(1428, 222);1428 mod 222 = 96
222 mod 96 = 30
96 mod 30 = 6
30 mod 6 = 0
Towers of Hanoi

The “Towers of Hanoi” is a popular disk-moving puzzle. You have three poles and n number of disks. All disks have different sizes. They are stacked on the first peg in order of their sizes. The largest disk is on the bottom, the smallest is on the top. The goal is to move all disks from peg 1 to peg 3 under the following restrictions:
- Only one disk can be moved at a time
- A larger disk can not be placed on top of a smaller disk
This puzzle can be solved using recursion.
const towersOfHanoi =(nDisks, start, auxiliary, end) => {
if (nDisks === 1) {
console.log("Disk 1 from " + start + " to " + end);
}
else {
towersOfHanoi(nDisks - 1, start, end, auxiliary );
console.log("Disk " + nDisks + " from " + start + " to " + end);
towersOfHanoi(nDisks - 1, auxiliary, start, end);
}
};The function towersOfHanoi() takes four arguments:
nDisks — the number of disks in the puzzle
start, auxiliary, end — the names of the three pegs
- First, we check if the number of disks,
nDisksis equal to one. If so, the disk will be moved from the start peg to the end peg. Weconsole.log()the operation to see the output. - If not, we call our recursive function. When we need to move
nDisks — 1from the start pole to the auxiliary pole, theauxiliarypeg becomes the end peg and theendpeg becomes the auxiliary peg. - Next, we
console.log()the movement of the disk on the pegs. - Finally, we call the recursive function again. Here, the
auxiliarypeg becomes the start peg and thestartpeg becomes the auxiliary peg.
Example output with nDisks = 3:
towersOfHanoi(3, 'A', 'B', 'C');Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C
Sorting Algorithms
A sorting algorithm is an algorithm that puts elements of a list in a certain order. There are different sorting algorithms used for different purposes.
Some work by moving elements directly to their final position, one at a time. You sort a list of n values, put the first value in place and continue sorting the next value. We are going to look at two similar algorithms, Bubble sort and Selection sort.
Other algorithms put items into a temporary position to their final position, re-scan the list, moving values closer to their final position with each iteration. Such algorithm is the Insertion sort algorithm.
Before starting with the implementation we will write a swap() function for swapping two numbers in a list which will be used for the algorithms. The function is as follows:
const swap = (array, firstIndex, secondIndex) => {
const tempNumber = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = tempNumber;
};Bubble Sort
Bubble sort is a simple algorithm mainly used as an introduction to sorting algorithms. It is a very inefficient algorithm for sorting large data volumes, as the array size grows, the time it takes to sort the array is increased quadratic.
- The algorithm starts at the right end of the list, comparing the numbers on their left and right sides. If the number on the right is found to be smaller, the numbers will be swapped.
- After the comparison is finished, it moves one position to the left and repeats the operation until it reaches the beginning of the list.
The implementation of the algorithm uses two recursive functions — one for sorting and the main for validation.
Let’s start with the implementation of the nested sorting function:
const sortNumbers = (array, currIndex = array.length - 1, swapped = false) => {
if(array[currIndex] < array[currIndex - 1]){
console.log(`Swap: ${array[currIndex]} with ${array[currIndex - 1]}`)
swap(array, currIndex, currIndex -1);
swapped = true;
}
if(currIndex === 0){
return swapped;
}
return sortNumbers(array, currIndex - 1, swapped);
}The function takes three arguments:
array — the collection of values
currIndex — current index in the array starting from the last index by default
swapped — Boolean value to define if numbers have been swapped
- Initially, we check if the last current value is smaller than the value before. If so, we
console.log()the change and swap the values. We also set theswappedvariable to true as a swap operation has been done. - Next, we validate if the function has iterated through the whole collection. If so, we return the swapped variable as a reference of the operation.
- Finally, we call the
sortNumbers()function again by passing the updatedarray, the next index from right to the left side and theswappedvalue.
Implementation of main bubbleSort() function:
const bubbleSort = (array) => {
const swapped = sortNumbers(array);
if(!swapped){
return array;
}
return bubbleSort(array);
}The function takes one argument:
array — the collection of values
- We start by declaring a
swappedconstant which is populated by oursortNumbers()function. - Next, we check if numbers have been swapped or not. If numbers have not been swapped, this means that the collection is fully sorted and we return the
array. - Otherwise, we call back our function by passing the updated
array.
Example output:
const numbers = [2,-1,0,8,5,7,4,3,1,9,6];
bubbleSort(numbers);Swap: 6 with 9
Swap: 1 with 3
Swap: 1 with 4
Swap: 1 with 7
Swap: 1 with 5
Swap: 1 with 8
Swap: -1 with 2
Swap: 3 with 4
Swap: 3 with 7
Swap: 3 with 5
Swap: 3 with 8
Swap: 0 with 2
Swap: 4 with 7
Swap: 4 with 5
Swap: 4 with 8
Swap: 1 with 2
Swap: 6 with 7
Swap: 5 with 8
Swap: 6 with 8
Swap: 7 with 8
Selection Sort
This algorithm uses a linear search to find the smallest value located in the list. The smallest value swaps with the leftmost number and is consider fully sorted. If the smallest value happens to already be in the leftmost position, no operation is carried out. The same operation is repeated until all of the values are fully sorted.
Implementation of Selection Sort:
The implementation of this algorithm will consist of two recursive functions. Let’s first see an implementation of finding the smallest value.
const findNextSmallNumber = (array, smallValIndex, nextIndex)=>{
if(array[smallValIndex] > array[nextIndex]){
smallValIndex = nextIndex;
}
if(array.length - 1 === nextIndex){
return smallValIndex;
}
return findNextSmallNumber(array, smallValIndex, nextIndex + 1);
}The function takes three arguments:
array — the list of values
smallValIndex — the index of the current small number
nextIndex — the index of the next number in the list
- First, we check if our current small value is greater than the next value. If so, we set the value of the
smallValIndexto the index of the next value. - Next, we make sure that whether we have checked each value in the list. If so, we return the index of the smallest value —
smallValIndex. - Finally, we call the recursive function with the list, the current state of
smallValIndexandnextIndexincremented by 1 to check the next value in the list.
Implementation of main selectionSort():
const selectionSort = (array, currIndex = 0) => {
if(array.length - 1 === currIndex || array.length <= 1){
return array;
}
const minValueIndex = findNextSmallNumber(array, currIndex, currIndex+1);
console.log(`Swap ${array[currIndex]} with ${array[minValueIndex]}`);
swap(array, currIndex, minValueIndex);
return selectionSort(array, currIndex+1);
}The function selectionSort() takes two arguments:
array — the list of values
currIndex — the index of the current number — 0 by default
- First, we check if the
currIndexis equal to array’s length or if there are only 1 or no items in the list and return the array if that is true. This is the break point of the recursive function. - Next, we find the smallest value index by calling the recursive function
findNextSmallNumber(). As described above the function takes the current index that needs sorting as thesmallValIndex. Also passingcurrIndex+1as the next index indicates the start point of the unsorted numbers. console.log()how numbers swap between each other.- We swap the places of the current number and the minimum value.
- Finally, we call the function again by passing the current state of the array and increment the
currIndexby one to check for the next number.
Example output with array = [2,-1,0,8,5,7,4,3,1,9,6] :
const numbers = [2,-1,0,8,5,7,4,3,1,9,6];
selectionSort(numbers);Swap 2 with -1
Swap 2 with 0
Swap 2 with 1
Swap 8 with 2
Swap 5 with 3
Swap 7 with 4
Swap 7 with 5
Swap 7 with 6
Swap 8 with 7
Swap 9 with 8
Insertion Sort
Insertion sort is an algorithm that builds the final sorted collection one item at a time, inserting each in its suitable place among those already considered.
- It loops over positions in the array, considering the leftmost number fully sorted.
- From the remaining numbers, the leftmost number is taken out and compared to the already sorted number to its left. If the sorted number is larger, the two numbers swap. This operation repeats until either a smaller number appears, or the number reaches the leftmost side.
- The same operation is repeated until all of the numbers are fully sorted
Implementation of Insertion sort algorithm
The following implementation consists of two functions and the first one we will talk about is the nested function sortNumbers().
const sortNumbers = (array, prevIndex, currNumber) => {
if(prevIndex >= 0 && array[prevIndex] > currNumber){
array[prevIndex+1] = array[prevIndex];
}
else{
return prevIndex;
}
return sortNumbers(array, prevIndex-1, currNumber)
}The function takes three arguments:
array — the collection of values
prevIndex — the index of the previous number
currNumber — the current unsorted number
- Start by checking if the
prevIndexis greater or equal to the first index and if the previous number is larger than the current one. If so, set the previous number to the position of the current number. - If that is not the case return the index of the previous number.
- Finally, callback the function by passing the same function, except decremented the previous index by one.
- The function sets the position of the larger number to the position of the small number and sends back the index of the smallest number.
Let’s see why.
Implementation of insertionSort() :
const insertionSort = (array, currIndex = 1) => {
const currNumber = array[currIndex];
const smallValIndex = sortNumbers(array, currIndex-1, currNumber);
if(array[smallValIndex+1] !== currNumber){
array[smallValIndex+1] = currNumber;
}if(currIndex === array.length - 1){
return array;
}
return insertionSort(array, currIndex + 1);
}
The function takes two arguments:
array — the collection of values
currIndex — the index of the current number starting from 1 by default. The first number with currIndex = 0 is considered sorted
- The current number is set to a constant
currNumber. - The index of the smallest value of the sorted numbers is set to
smallValIndexreturned bysortNumbers()function where we pass the array, the previous number (currIndex-1) and the current number. - Once we get the smallest value index, we make sure that current number is different than the number after the smallest value. If so, we set the current number to that position.
- Next, we check if the end of the array is reached and if so, the array is returned.
- Finally, the function is called again by passing the index of the next number
currIndex+1.
Thanks for reading! Feel free to comment and ask questions, and stay tuned for more. Feel free to play with the algorithms and adjust them so they can be useful to you.
