Understanding FP: Overcoming Intuition and Ease Hurdles (loops vs. recursion)
Tags: functional, scala, rust, javascript
Published: 2023-04-06 02:36:34

📹 Hate reading articles? Check out [the complementary video](https://youtu.be/VTedRObg5WM), which covers the same content.

---

Some people state that the FP way of doing things is easier, while others say it’s more complicated and isn’t even worth it. Let’s explore this. 

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

And at the end, I’ll 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 we’ll keep switching languages).

```jsx
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.

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

print(0)
```

![Droste](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ewyj971x017r15k40ea0.png)

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 it’s not there, searches the parent, and so on” In other words, this is the expected results:

```jsx
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]}}}) // 40
search(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:

```jsx
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 (I’ve turned the outer loop into a recursion):

```jsx
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 didn’t 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 you’re 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, it’s not as apparent. Why would this alien functional concept be any better? It’s common to hear: “I’ve been doing X for years, and it’s okay; why would I relearn for no reason?!”

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

First, quick spoiler, loops and recursions aren’t actually rivals; as I’ll 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 shouldn’t 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.

Let’s go back to iterations. Let’s 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.

We’ve already seen loops. This time let’s ask ourselves what **decisions** we must make when writing a for-loop.

```jsx
let numbers = [-1, 2, 3, 4, 5]

let sum = 0
for (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, let’s pretend we don’t have to worry about the state outside .*

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

```jsx
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 don’t 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. Let’s see what languages offer these days.

### Alternatives

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

```rust
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:

```scala
val numbers = List(-1, 2, 3, 4, 5)

var sum = 0
for number <- numbers
do sum += number

println(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:

```scala
val numbers = List(-1, 2, 3, 4, 5)

var sum = 0
for
  number <- numbers if number > 0
  square = number * number
do sum += square

println(s"The sum is $sum")
// Prints: The sum is 54
```

These constructs are more functional than the JavaScript loops we’ve 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).

---

💡 Rust’s for-loop syntax is syntactic sugar for [iterators](https://doc.rust-lang.org/std/iter/trait.Iterator.html), which are responsible for the logic of iterating over some items.

---

💡 Scala’s for-comprehension is syntactic sugar for a sequence of calls to these methods: `foreach`, `map`, `flatMap`, and `withFilter`, which can be used on any type that defines these methods.

---

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

```rust
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
```

```scala
val numbers = List(-1, 2, 3, 4, 5)

val sum = numbers.filter(_ > 0).map(n => n * n).sum

println(s"The sum is $sum")
// Prints: The sum is 54
```

We say: filter these out, square the numbers, and then sum them up. We don’t 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.


```scala
// From
val responses: List[Either[String, Int]]

// To
val result: Either[String, List[Int]]
```

Each result is represented by the `Either` type (like [`Result`](https://doc.rust-lang.org/std/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:

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

```scala
// If there is at least one error
List(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:

```scala
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).

```scala
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 shouldn’t deal with internal accumulators. We can wrap it up like a candy (or a sausage) and expose only what’s needed:

```scala
def process(results: List[Either[String, Int]]): Either[String, List[Int]] =
  go(results, List.empty)

// internal, recursive function
def go(
    results: List[Either[String, Int]],
    accumulator: List[Int]
): Either[String, List[Int]] = ???
```

---

💡 This pattern is quite common, see [recursive go](https://kowainik.github.io/posts/haskell-mini-patterns#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). Let’s show it with a skeleton:

```scala
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 doesn’t 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!

```scala
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:

```scala
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 we’re looking at a **failure**, that’s it; we’re done, and we can just return it – we don’t care about the rest of the list and accumulated values:

```scala
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 it’s 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:

```scala
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 that’s it.

```scala
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`.

```scala
import cats.implicits._

def process(results: List[Either[String, Int]]): Either[String, List[Int]] =
  results.sequence
```

```scala
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 that’s it. There are no tricks or magic behind it. Here is the beauty and power of functional programming. It’s 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 don’t 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 don’t need to change the body:

```scala
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.

---

{% embed https://youtu.be/VTedRObg5WM %}