Functional loops in JavaScript
The lack of loop constructs is probably a top source of pain while learning functional programming languages. Back in the day, when I was learning Erlang, I wondered how these guys got even the most straightforward algorithms to work without using loops. I mean, you need some form of a loop to print numbers from 1 to 10, right?
Soon thereafter, I realized that the lack of loops didn’t mean that you couldn’t iterate over sequences of elements but rather that you had to go with alternative techniques. (i.e., recursive algorithms.)
Today, we are going to explore how we can sum all the numbers on a list without using loops.
We are going to start from an iterative approach and move to a recursive variant while exploring a functional implementation in between.
To keep the code portable, we are not going to use Array’s built-in functions like map, reduce, and so on. The idea is that you can take the code and port it to your language of choice with little to no effort.
Let’s start with the iterative approach.
Iterative Approach — JavaScript
The most commonly used technique to sum numbers on a list is the iterative approach. That is “looping” over the list of numbers, adding them to an accumulator, and returning that accumulated value once the list gets exhausted.
function sum(numbers) {
let acc = 0;
for (let n of numbers) {
acc += n;
}
return acc;
}Maybe it’s not the most elegant solution, but I guess we could agree that it gets the job done.
Also, assuming there are no tail call optimizations in place, this variant is less expensive than a recursive algorithm.
Functional Approach — Erlang
To see a real “functional loop” in action, we are going to port our little program to Erlang. A purely functional programming language.
If you have never seen an Erlang program before, the syntax might look a bit cryptic, but the program is really simple:
- Splits the list into a head/tail structure.
- Adds the value of the head to the accumulator.
- Calls the “sum” function using the tail and the new value of the accumulator.
This operation keeps going until the list gets exhausted and the accumulator is returned to the caller.
% Entry point.
sum(L) ->
sum(L, 0).% Recursive call.
sum([H|T], Acc) ->
sum(T, H + Acc);% Base case
sum([], Acc) ->
Acc.
What’s cool about this program is that it shows us how to sum all elements in a list without using loops. (Incidentally, there is no other way in Erlang.)
Anyways, now that we know that it is possible to sum elements using only recursive calls let’s try to replicate this Erlang program in JS.
Recursive Approach — JavaScript
Since JS doesn’t have any built-in mechanism to split an array into a [head|tail] structure, we are going to start from there and create our own helper functions.
The first one will be a function that returns the “head node” of a list.
function head(list) {
return len(list) > 0
? list[0]
: null;
}Note: “len” is a custom function that performs a null check and returns the number of elements on the given list. You can see the function’s code in the gist linked down below.
The second function will be another helper that returns the “tail” of the list. That’s all the elements in the list except the first one. If the list has less than two items, its tail is considered to be null.
function tail(list) {
return len(list) > 1
? list.splice(1)
: null;
}Believe it or not, with only these functions in place, we have everything we need to iterate over a sequence without using loops. Now let’s implement the recursive version of the “sum” function to see these helpers in action.
// Entry point.
function sum(list) {
return recSum(list, 0);
}function recSum(list, acc) {
const h = head(list);
if (!h)
// Base case.
return acc; // Recursive call.
return recSum(tail(list), h + acc);
}
Depending on your background, you might find the recursive algorithm cleaner and elegant, or maybe a bit overwhelming given that it just adds numbers!
In any case, the key takeaway from this exercise is:
Every iterative algorithm can be converted into a recursive variant.
I hope this concept will help you with coding interviews or school assignments like: “Write a program to find the mean value in a sequence blah, blah, blah… without using loops!”.
I guess that’s all there is for this short post. I hope that you find it useful.
I’d probably write a short series about recursion covering practical use cases, pitfalls, time complexity, recursive data structures, performance, quadratic behavior, and so on. If you are into recursion, stay tuned!
Thanks for reading, and don’t forget to clap if you like this post!
Before you go. If you are getting started with algorithms and data structures, you might want to take a look at my ebook “Data Structures From Scratch — JS Edition.” (It’s free for Kindle Unlimited members.)
