Understanding FP: Overcoming Intuition and Ease Hurdles (loops vs. recursion)

Hate reading articles? Check out the complementary video, which covers the same content.

Some people state that the FP way of doing things is easier, while others say its more complicated and isnt even worth it. Lets explore this.

To not go too abstract, lets anchor around iterating over data structures: loops, recursion, and other alternatives.

And at the end, Ill walk through solving a little interview task to tie it all together.

Loop and recursion

I assume you know what a loop is. Loops are a fundamental concept in imperative programming.

Here is a typical for-loop in JavaScript (note that well keep switching languages).

for (let i = 0; i < 5; i++) {  console.log(i)}

This code prints numbers from 0 up to 5.

Then there is recursion, which is less popular among programmers, but nevertheless fundamental: in math, computer science, and everywhere else.

function print(n) {  if (n < 5) {    console.log(n)    print(n + 1)  } }print(0)

Both can be used to solve similar sorts of problems. So, which one is better? What if we look at an example?

Here is a simple problem: Given an object that has an items field and an optional parent, write a function that searches for needle: first, among its items, and if its not there, searches the parent, and so on In other words, this is the expected results:

search(40, {items:[1,40,3]}) // 40 (in items)search(40, {items:[1,2,3], parent: {items:[1,40]}}) // 40 (in parent's items)search(40, {items:[1,2,3], parent: {items:[1,2], parent: {items:[40]}}}) // 40search(40, {items:[1,2,3], parent: {items:[1,2], parent: {items:[]}}}) // null

If the search feels useless, imagine it is searching for a whole object by name or something.

We can write this using two for-loops:

function search(needle, scope) {  for (let cur = scope; cur !== null; cur = cur.parent) {    for (let i = 0; i < cur.items.length; i++) {      const item = cur.items[i]      if (item === needle) {        return item      }    }  return null}

• Outer loop: We start with a current scope and visit all the parents while they exist.
• Inner loop: We go through the items (by index from 0 till the last one).
• We break as soon as we find a desired object; otherwise, we return null

Alternatively, we can write this using a recursion (Ive turned the outer loop into a recursion):

function search(needle, scope) {  for (let i = 0; i < scope.items.length; i++) {    const item = scope.items[i]    if (item === needle) {      return item    }  }  if (scope.parent) {    return search(needle, scope.parent)  } else {    return null  }}

We still go through all the items in the scope.

• If we didnt find the object and the parent exists, we rerun the function for the parent.
• Otherwise, we return null

Both of these work, but there is no punch line yet.

Intuition and Ease

Even if youre new to the functional programming scene, somebody has probably tried to convince you how superior it is recursion and FP in general how easy and powerful some FP concepts or techniques are compared to an alternative.

And if you already have some experience with FP, you might be guilty of this yourself. It happens to us constantly: a new concept clicks, and we want to climb the tallest tree to share it with everyone else because it made our lives so much better!

But to a newcomer or a bystander, its not as apparent. Why would this alien functional concept be any better? Its common to hear: Ive been doing X for years, and its okay; why would I relearn for no reason?!

And then we have a stalemate. I have a hunch that its mainly due to a bit of miscommunication or misperception and the hurdles of trying a new concept.

First, quick spoiler, loops and recursions arent actually rivals; as Ill show later, there are different kinds of loops and various other ways to iterate.

Second, hurdles such as intuition and ease can make it challenging to try a new concept. It may not immediately make sense when we encounter a new way of doing things.

But we shouldnt expect to grasp ideas intuitively. Some concepts may be easy to understand and require little effort, while others may be more complex and require more time.

Lets go back to iterations. Lets reexamine a basic for-loop and a basic recursion, but then look at what people really do in production these days.

To loop or not to loop?

Note that there are many different ways to iterate over data structures:

• for-loops;
• recursion;
• iterators;
• list-comprehensions;
• combinators/operators/pipelines;
• while-loops (why would you do this to yourself?);
• etc.

Weve already seen loops. This time lets ask ourselves what decisions we must make when writing a for-loop.

let numbers = [-1, 2, 3, 4, 5]let sum = 0for (let i = 0; i < numbers.length; i++) {  sum += numbers[i]}console.log(`The sum is ${sum}`)// Prints: The sum is 13

• Where do we start? In this case: i is 0, and sum is 0.
• Where do we stop? In this case: we go until the end of numbers using its length.
• How to iterate? Or what is the step? In this case: we bump i by 1.
• What to do on each step? In this case: add the current number to the sum.
• And, for now, lets pretend we dont have to worry about the state outside .

So, at least four decisions for a for-loop. Okay, what about recursion?

let numbers = [-1, 2, 3, 4, 5]function sumList(numbers) {  if (numbers.length === 0) {    return 0  } else {    const [head, ...tail] = numbers    return head + sumList(tail)  }}console.log(`The sum is ${sumList(numbers)}`)// Prints: The sum is 13

Recursive function comprises 2 parts: the base and the recursive cases.

• The base case is the condition to stop the recursion.
• The recursive case is where the function calls itself.

• What is the base case? In this case: if the list is empty, return 0.
• What is the recursive case? In this case: add the current number to the sum of the rest of the numbers.
• Additionally: What is the initial input to the recursive function? In this case, we pass numbers intact, but sometimes we need to adopt the given data, for example, reverse the input list or pass some accumulator.

We have to make fewer decisions using recursion, which is neither exciting nor crucial. The crucial part is the nature of our decisions notice that we moved from how to do something to what to do.

We dont worry about how the code runs: where to start, where to end, and how to iterate; we specify what we want to achieve.

This is the shift we have to do. And this is the property that functional programmers prefer.

But this property is not tied to recursions. Lets see what languages offer these days.

Alternatives

Rust, for instance, has a more concise for-loop alternative; here is a way to sum numbers:

let numbers = vec![-1, 2, 3, 4, 5];let mut sum = 0;for number in numbers {    sum += number;}println!("The sum is ${sum}");// Prints: The sum is 13

And, the same in Scala, we can use for-loop or for-comprehension:

val numbers = List(-1, 2, 3, 4, 5)var sum = 0for number <- numbersdo sum += numberprintln(s"The sum is $sum")// Prints: The sum is 13

Moreover, we can add some transformation and filtering; for example, to sum the square of positive numbers:

val numbers = List(-1, 2, 3, 4, 5)var sum = 0for  number <- numbers if number > 0  square = number * numberdo sum += squareprintln(s"The sum is $sum")// Prints: The sum is 54

These constructs are more functional than the JavaScript loops weve started with we no longer have to worry about the hows.

Also, in both languages, this is just a special syntax for using functions (or methods, or operations, or combinators, or pipelines, or whatever you want to call it).

Rustsfor-loop syntax is syntactic sugar foriterators, which are responsible for the logic of iterating over some items.

Scalas for-comprehensionis syntactic sugarfor a sequence of calls to these methods: foreach, map, flatMap, and withFilter, which can be usedon any type that defines these methods.

So, these (and other) functions can often be directly used to achieve the same results more concisely:

let numbers = vec![-1, 2, 3, 4, 5];let sum: i32 = numbers    .iter()    .filter(|&n| *n > 0)    .map(|x| x * x)    .sum();println!("The sum is ${sum}");// Prints: The sum is 54

val numbers = List(-1, 2, 3, 4, 5)val sum = numbers.filter(_ > 0).map(n => n * n).sumprintln(s"The sum is $sum")// Prints: The sum is 54

We say: filter these out, square the numbers, and then sum them up. We dont worry about the type of the collection, how many elements it has, how to traverse it, etc.

A practical walkthrough

aka How I usually go about solving a problem using recursion

Imagine we have a problem:

1. We have a list of responses from different services.
2. Each response is either a successful number or a failure message.
3. We need to return one result:
   • either a list of all successful numbers if there are no failures,
   • or the message of the first failure.

// Fromval responses: List[Either[String, Int]]// Toval result: Either[String, List[Int]]

Each result is represented by the Either type (like Result in Rust):

• Right represents success and contains a value (in our case, a number).
• Left represents failure and contains an error value (in our case, an error message).

These are the example inputs and outputs:

// If all the responses are successful List(Right(1), Right(25), Right(82))// The result should be: // Right(List(1, 25, 82))

// If there is at least one errorList(Right(1), Right(25), Left("boom"), Right(82), Left("boom 2"))// The result should be:// Left("boom")

We start with this question: What is the (initial) input to the recursive function?

Do we need all the elements? Yes, there is no way around it; we need to process the results:

def process(    results: List[Either[String, Int]]): Either[String, List[Int]] = ???

Do we need anything else? Here is a reminder:

• If there is an error, we return that element right away.
• If there are no errors, we must accumulate (keep track of) all the successful values.

So, while going through the results, we have to accumulate some values: we start with an empty list (and when we see a successful one, we append it to the list).

def process(    results: List[Either[String, Int]],    accumulator: List[Int]): Either[String, List[Int]] = ???process(results, List.empty)

This is not the finest interface users shouldnt deal with internal accumulators. We can wrap it up like a candy (or a sausage) and expose only whats needed:

def process(results: List[Either[String, Int]]): Either[String, List[Int]] =  go(results, List.empty)// internal, recursive functiondef go(    results: List[Either[String, Int]],    accumulator: List[Int]): Either[String, List[Int]] = ???

This pattern is quite common, see recursive go.

Now we can think about the recursion cases. We recurse over a list; a list is either empty (Nil in Scala) or has elements. Additionally, we can split a list as a head (first element) and a tail (the rest of the elements). Lets show it with a skeleton:

def go(    results: List[Either[String, Int]],    accumulator: List[Int]): Either[String, List[Int]] = results match {  case head :: rest => ???  case Nil          => ???}

What is the base case? The recursion stops when the list ends (or doesnt even begin) when the list is empty. It means there are no errors, and we return success. accumulator should contain all the successful values:

• if the original list is empty, accumulator is empty;
• otherwise, accumulator contains all the numbers. Success!

def go(    results: List[Either[String, Int]],    accumulator: List[Int]): Either[String, List[Int]] = results match {  case head :: rest => ???  case Nil          => Right(accumulator)}

What is the recursive case? On every step, we have to decide what to do with a head, a tail, and calling the recursion. What is head? It contains a current value, which is either a successful number or a failure message:

def go(    results: List[Either[String, Int]],    accumulator: List[Int]): Either[String, List[Int]] = results match {  case Left(failure) :: rest => ???  case Right(result) :: rest => ???  case Nil                   => Right(accumulator)}

If were looking at a failure, thats it; were done, and we can just return it we dont care about the rest of the list and accumulated values:

def go(    results: List[Either[String, Int]],    accumulator: List[Int]): Either[String, List[Int]] = results match {  case Left(failure) :: rest => Left(failure)  case Right(result) :: rest => ???  case Nil                   => Right(accumulator)}

And if its a successful value?

• We add it to the accumulator.
• We keep the recursion going, we have to iterate through the rest of the list.

We call the go function again, but this time the input is the rest of the list, and accumulator contains another successful value:

def process(results: List[Either[String, Int]]): Either[String, List[Int]] =  go(results, List.empty)def go(    results: List[Either[String, Int]],    accumulator: List[Int]): Either[String, List[Int]] = results match {  case Left(failure) :: rest => Left(failure)  case Right(result) :: rest => go(rest, accumulator :+ result)  case Nil                   => Right(accumulator)}

And thats it.

process(List(Right(1), Right(25), Right(82))// Right(List(1, 25, 82))process(List(Right(1), Right(25), Left("boom"), Right(82), Left("boom 2")))// Left("boom")

Alternatives

Remember how we talked about alternatives?

We can refactor our process using a standard function called sequence.

import cats.implicits._def process(results: List[Either[String, Int]]): Either[String, List[Int]] =  results.sequence

process(List(Right(1), Right(25), Right(82))// Right(List(1, 25, 82))process(List(Right(1), Right(25), Left("boom"), Right(82), Left("boom 2")))// Left("boom")

And thats it. There are no tricks or magic behind it. Here is the beauty and power of functional programming. Its also reusable and quite common, for example:

• You sent multiple requests, and one service failed. You can just abort all the other operations and return the failure you dont have to wait or waste resources.
• Same with accessing a database.
• Parsing some data you got from the frontend.

If we change the type, for instance, to optional values, we dont need to change the body:

def process(results: List[Option[Int]]): Option[List[Int]] =  results.sequence

Final words

If you wrote thousands of loops, will writing recursion for the first time be easy? No.

Will it be very beneficial? Well, depends on your goals. If you want to impress your colleagues, probably not. If you have long term goals or aim to expand your horizon? Perfect!

After writing hundreds (or thousands) of loops and recursion, do I prefer a recursion to a loop? Yes, anytime.

Do I prefer using a combinator or a nicer comprehension syntax? Yes, most of the time. But recursion is an excellent tool for some jobs.