## DEV Community

Vince Campanale

Posted on • Originally published at vincecampanale.com

# Using Recursion to Loop in Elm

This post is centered on the following problem:

``````Find the difference between the square of the sum and the sum of the squares of the first N natural numbers.

The square of the sum of the first ten natural numbers is (1 + 2 + ... + 10)² = 55² = 3025.

The sum of the squares of the first ten natural numbers is 1² + 2² + ... + 10² = 385.

Hence the difference between the square of the sum of the first ten natural numbers and the sum of the squares of the first ten natural numbers is 3025 - 385 = 2640.
``````

Credit for the problem goes to exercism.io.

The plan is to first solve it with a `for` loop in Javascript, then solve it with recursion in Javascript, and finally translate the recursive solution to Elm.

### With a `for` Loop

The `for` loop solution, in barely-pseudocode looks like this:

``````-- get the square of the sum of n by:
-- going from 1 to n
-- and adding each number to a total
-- return the total after the loop is done

-- get the sum of the squares of n by:
-- going from 1 to n
-- and adding the square of each number to a total
-- return the total after the loop is done

-- subtract the latter from the former
``````

Translated to Javascript, we get this:

``````function squareOfSum(number) {
let sum = 0;
for (let i = 1; i <= number; i++) {
sum += i;
}
return Math.pow(sum, 2);
}

function sumOfSquares(number) {
let sum = 0;
for (let i = 1; i <= number; i++) {
sum += Math.pow(i, 2);
}
return sum;
}

function difference(number) {
return squareOfSum(number) - sumOfSquares(number);
}

console.log(difference(10) === 2640); // true
``````

Thanks to my extensive test suite, I can confidently refactor and use recursion instead.

### In Order to Understand Recursion...

The recursive equivalent of the above solution goes like this:

``````-- get the square of the sum of n by:
-- getting the triangular number for n by:
-- returning 0 if n is 0
-- adding n to the triangular number of n - 1

-- get the sum of the squares of n by:
-- returning 0 if n is 0
-- adding the square of n to the sum of the squares of n - 1

-- subtract the latter from the former
``````

So, recursion is acting as a different way of looping by defining an action for each number `n` down to 1 and a final action to end the loop when `n` gets to 0.

I googled "factorial with adding instead of multiplying" and found "triangular numbers", so the function for calculating the sum of positive integers from 1 to `N` is called `triangulate` 🤷🏻‍♂️.

Let's write that function first:

``````function triangulate(n) {
if (n === 0) {
return 0;
} else {
return n + triangulate(n - 1);
}
}

// which can be simplified to:

function triangulate(n) {
return n === 0 ? 0 : n + triangulate(n - 1);
}
``````

Using the triangulate function, we can get the `squareOfSum` function:

``````function squareOfSum(n) {
const sum = triangulate(n);
return Math.pow(sum, 2);
}
``````

The `sumOfSquares` function can also use recursion:

``````function sumOfSquares(n) {
if (n === 0) {
return 0;
} else {
return Math.pow(n, 2) + sumOfSquares(n - 1);
}
}

// again, can be reduced to..

function sumOfSquares(n) {
return n === 0 ? Math.pow(n, 2) + sumOfSquares(n - 1);
}
``````

One final thought on the Javascript solution is to make `triangulate` a bit more generic and add a second parameter for an exponent.

``````const triangulate = (n, exp = 1) =>
n === 0
? 0
: Math.pow(n, exp) + triangulate(n - 1, exp);
``````

Then `sumOfSquares` can be written as the following:

``````function sumOfSquares(n) {
return triangulate(n, 2);
}
``````

Elm doesn't have `for` loops. Whaaaaa

Yea, for real.

Luckily, we already know this problem can be solved without a `for` loop. So what's the Elm equivalent of the recursive solution above? Well, let's refactor `sumOfSquares` just one more time in Javascript, using a switch statement with only two cases this time.

``````function sumOfSquares(n) {
switch (n) {
case 0:
return 0;
default:
return Math.pow(n, 2) + sumOfSquares(n - 1);
}
}
``````

Elm has a `case` statement, so a nearly equivalent function will work:

``````sumOfSquares : Int -> Int
sumOfSquares n =
case n of
0 -> 0
_ -> (n ^ 2) + sumOfSquares (n - 1)
``````

We can apply a similar approach to `squareOfSum`:

``````squareOfSum : Int -> Int
squareOfSum n =
let
triangulate x =
case x of
0 -> 0
_ -> x + triangulate (x - 1)
in
(triangulate n) ^ 2
``````

Then the final function `difference` is just:

``````difference : Int -> Int
difference n =
(squareOfSum n) - (sumOfSquares n)
``````

And voila, we have solved a `for`-loop-friendly problem in Elm, a language with no `for` loop.

### A Better Way?

While we can use recursion to loop through the numbers between `0` and `N`, we can also make use of other utilities exposed in Elm Core.

For example, `List.range` and `List.sum` make this problem much easier.

``````import List exposing (map, range, sum)

square : Int -> Int
square n =
n ^ 2

squareOfSum : Int -> Int
squareOfSum n =
range 1 n |> sum |> square

sumOfSquares : Int -> Int
sumOfSquares n =
range 1 n |> map square |> sum

difference : Int -> Int
difference n =
squareOfSum n - sumOfSquares n
``````

Since `for` loops are one of the first things we learn as programmers, it's easy to fall back on `for` loops in solutions to everyday problems. Using Elm has taught me that `for` loops aren't necessary most of the time and seeking a different solution can lead to more declarative and readable code.

Here's another way to write `diff(n)` that computes in linear space and time. Another important distinction is the result is computed in a single `n`-sized loop instead of multiple loops

``````sq : Int -> Int
sq n =
n * n

diff : Int -> Int
diff n =
let
loop sum squares n =
if n == 0 then
sq sum - squares
else
loop (sum + n) (squares + sq n) (n - 1)
in
loop 0 0 n

diff 10 == 2640
``````

You could also implement `loop` generically using a union type and then implement `diff` with `loop`

``````type Loop state result
= Recur state
| Done result

loop : state -> (state -> Loop state result) -> result
loop init f =
case (f init) of
Recur state ->
loop state f

Done value ->
value

diff : Int -> Int
diff n =
loop ( 0, 0, n ) <|
\( sum, squares, n ) ->
if n == 0 then
Done (sq sum - squares)
else
Recur ( sum + n, squares + sq n, n - 1 )

diff 10 == 2640
``````

Both implementations are tail recursive and do not grow the stack