Previously, we covered immutable data structures and value equality which helps to avoid unexpected side effects. This article covers Higher-Order functions and recursion.

Imagine having a number and the task is to find out the sum of all the numbers from 1 to the given number. Pretty simple, right?

// Take a number and return the sum of all the numbers from 1 to that number.
// Example:
// sum(4) = 4 + 3 + 2 + 1 = 10

void main(List<String> args) {
    // Imperative approach
    final iterativeSumResult = iterativeSum(5);
    print(iterativeSumResult); // 15
}

// Takes in a number and returns the sum of all numbers from 1 to that number. \
// Iterative solution. (Imperative approach)
int iterativeSum(int number) {
    int result = 0;
    
    for (int i = 0; i < number; i++) {
        result += i;
    }
    
    return result;
}

Is anything wrong with the imperative approach? Technically, nothing wrong, but in the first article, we saw that FP aims to solve problems in a declarative way. So let’s dive in!

Recursion

Recursion is when a function calls itself again and again until a specific condition is met. It can also help us to break down complex problems into manageable chunks.

Recursion has two parts:

Base Condition: The base condition acts as an exit point for the recursive function. It is used to stop the recursive function calls.

Recursive Case: The recursive case is where the function keeps calling itself again and again. Now, let's solve the problem using recursion.

void main(List<String> args) {
    // Declarative approach
    final recursiveSumResult = recursiveSum(5);
    print(recursiveSumResult); // 15
}

/// Takes in a number and returns the sum of all numbers from 1 to that number. \
/// Recursive solution. \
/// Time complexity: O(n) \
/// Space complexity: O(n) \
/// n is the number of recursive calls. \
/// This is because the space complexity is the number of recursive calls. \
/// The space complexity is the number of recursive calls because the function \
/// calls itself. \
int recursiveSum(int number) {
    if (number == 0) return 0;
    
    return number + recursiveSum(number - 1);
}

For input 5, the function evaluates to 5 + _recursiveSum(5–1) which is 5 + _recursiveSum(4). Now, the next function call is with input 4 which evaluates to 4 + _recursiveSum(4–1) which is 4 + _recursiveSum(3) and so on until the base condition is reached.

Line no. 16 is the base condition. Upon reaching the base condition, we have 5 + 4 + 3 + 2 + 1 + 0lined up which adds up and returns the result.

Iteration vs Recursion

As seen, Iteration is imperative, and recursion is declarative. Iteration includes looping over the collection. We have to manage the state, so it’s stateful. For example, the _result variable was the state in the first example.

Recursion is self-referencing and stateless. We do not have to keep track of any state, which makes debugging applications easier. It is subjective, but recursion makes the code look more clean and elegant. However, for someone starting fresh it might be confusing to read and debug.

Reading and making sense of a code is easier when it is declarative. Whereas in imperative, one can not just look at the code and tell what exactly it is doing; one has to execute it at least mentally and then understand what the code does.

Alright! what about the performance?

Performance

Recursive functions are not as efficient as iterative ones. Most of the time, the iterative approach provides better performance when compared with recursion. Finding out complexity for a recursive function is not as straightforward as loops. Recursion, if not appropriately configured, leads to stack overflow errors.

But, How do we make recursive functions scalable and performant? One of the ways is to use Memoization(next article in the series) to reduce the computation cost.

Regarding the Stack overflow error, it occurs when there are too many function calls, this number is pretty significant though. Language needs to support Tail call optimization(TCO) to overcome this. Unfortunately, Dart does not support this because it is not supported by javascript, and for the web, Dart has to compile the code to javascript.

Because of such things, recursion often does not make its way into the production applications.

Higher-Order Functions (HOFs)

A function that takes a function as an argument or returns a function is a higher-order function. It is possible because functions are treated as first-class citizens in Dart.

You’ve already used higher-order functions if you have used any built-in array methods like where, map, or reduce.

Filter

The filter takes a predicate function and an array and returns a new list with only those values for which the predicate function returns true.

Imagine writing a program to filter out all the even numbers from the list.

Imperative: Involves a for loop and a state to maintain the results. There is nothing wrong, but it is not as readable compared to the other solutions.

.where: Dart list supports an equivalent to the filter function, the where method. It takes a predicate function and returns a new Iterable (.toList can be used to return a list instance). It is declarative and tells exactly what the code does.

Functional API: It is similar to the where method, but since we are learning FP, let’s implement using the Functional APIs as well. The filter function takes a predicate function and an array and returns a new list. It is also declarative.

Map

The map works the same way as a filter, except that instead of taking a predicate function, it takes a mapper function, applies it to each element from the list, and returns a new list.

Imagine writing a program to double all the elements in the list.

import '../utilities/utilities.dart';

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

void main() {
  // Imperative approach
  final result = <int>[];

  for (final element in arr) {
    if (element.isEven) {
      result.add(element);
    }
  }

  print(result); // [2, 4, 6, 8, 10]

  // Declarative approach: .where in Dart lists
  final result2 = arr.where((element) => element.isEven).toList();
  print(result2); // [2, 4, 6, 8, 10]

  // Declarative approach: Functional API
  final evens = filter<int>(isEven, arr);
  print(evens); // [2, 4, 6, 8, 10]

  final odds = filter<int>

Similar to filter, the declarative approach looks much cleaner and readable.

flatMap

flatMap is a combination of map and flatten. Before jumping into the definition let's understand what flatten means.

Flatten returns a new collection by taking every element in the collection, and its subcollection and putting everything into a new collection with a single depth.

For instance, [1, 2, [3, 4], 5, [6, 7, [8, 9]]] will convert to [1, 2, 3, 4, 5, 6, 7, 8, 9] . It is flattening the collection.

The flatMap takes a function and applies it to every element in the collection, and its sub-collection. After mapping, it flattens the list. It is equivalent to the map method followed by a flat method.

final arr = IList.from([
    1,
    2,
    IList.from([3, 4]),
    5,
    IList.from([6, 7, 8]),
    9
]);

/// [arr] is a nested list and lets assume we get such a list from an API \
/// But, we want to flatten it to a single list of integers. \

void main(List<String> args) {
    // IList from the dartz package
    final result = arr.flatMap<int>(
        (a) {
            if (a is IList<int>) return a;
            
            if (a is int) return IList.from([a]);
            
            return IList.from([]);
        },
    );
    
    print(result);
}

flatMap definition: IList<B> flatMap<B>(Function1<A, IList<B>> f) .

Reduce

It is one of the most dreaded and underrated methods I have come across. It reduces a collection into a single value by combining all the elements using the passed-in function. Unfortunately, the definition does not reveal much if hearing it for the first time, but let’s understand with an example.

Let’s write a program to return a sum of all the numbers in the collection.

Imperative

int sumAllImperative(List<int> arr) {
    int sum = 0;
    
    for (final item in arr) {
        sum += item;
    }
    
    return sum;
}

As we have already seen in the earlier examples, we need to keep track of a state for the imperative approach and use a for loop to iterate over all the elements.

Declarative

Reduce takes in an initial value, a reducer function, and returns the accumulated value. The reducer function is a two-argument function that takes (1) an element from the list and (2) an accumulator, which is the result of the previous reduction. This reducer function is applied to every element of the list.

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

void main(List<String> args) {
    // Functional API
    final result = reduce<int>(
        (accumulator, element) => accumulator + element,
        arr,
        0,
    );
    
    print(result); // 55
}

For the first call, the accumulator is set to 0 (the initial value we passed in), and the element is 1(the first element from the list), and it evaluates to — 0 + 1 = 1. So now 1 in the accumulated value.

For the 2nd call, the accumulator is 1, and the element is 2, which evaluates to 1 + 2 = 3. So now the new accumulator value is 3.

For the 3rd call, the accumulator is 3; the element is 3, which evaluates to 3 + 3 = 6. The new accumulator value is 6.

For the 4th call, the accumulator is 6; the element is 4, which results in 10, which is the new accumulator value. So it goes on for all the items in the list, and finally, the accumulated value is returned.

Dart’s reduce and fold

Dart list supports reduce and fold method.

/// Reduce Implementation \
/// Reduces the [Iterable] to a single value. \
/// Starting accumulator is the first element of the [Iterable] \
/// For every other steps, Accumulator is the result of the previous reduction. \
/// Input: [0, 1, 2, 3, 4, 5] \
/// Step 1: Accumulator = 0 & element = 1 | accumulator + element = 1 \
/// Step 2: Accumulator = 1 & element = 2 | accumulator + element = 3 \
/// Step 3: Accumulator = 3 & element = 3 | accumulator + element = 6 \
/// Step 4: Accumulator = 6 & element = 4 | accumulator + element = 10 \
/// Step 5: Accumulator = 10 & element = 5 | accumulator + element = 15 \
int sumAllReduce(List<int> arr) => arr.reduce(
    (accumulator, element) => accumulator + element,
);

/// Fold Implementation \
/// Similar to reduce, but we can pass in the initial value of the accumulator. \
int sumAllFold(List<int> arr) => arr.fold(
    0,
    (accumulator, element) => accumulator + element,
);

The reduce method works similar to the reduce function we just saw, but it takes the first element from that list as the initial value. So if we want to use the inbuilt function, how do we pass the initial value?

The fold method works the same as the reduce method, but it lets us pass the initial value.

Final Thoughts

So to summarise, recursion and higher-order functions can be used to avoid loops. It, By default, will not increase the performance of the applications but is preferred because of its declarative nature. Furthermore, HOFs can be chained, which creates a pipeline through which the data can flow. The following article will cover memoization and how it helps minimize computation and improve the performance of the applications.

Awesome! Pat yourself on the back for reaching till the end. I hope I added some value to the time you invested. Find out more examples on the GitHub repository, and reach out on Twitter or LinkedIn for suggestions/Questions or any topic you’d like me to cover. You can support it by clapping👏, and thanks for reading :) Follow for more😄

Until next time, folks!