# Looping via Recursion

In most OO languages, one writes loops using `while` and `for`. Looping in that matter makes it very easy to introduce impure code. So, in FP languages, one writes loops using recursion, pattern-matching, and tail-call optimization. The rest of this file will compare OO code to its FP counterpart

## For `i` until `condition` do `computation` and then increment `i`

``````// factorial
var count = 5;
var result = 1;
for (var i = 2; i < count; i++) {
result = result * i
}
``````
``````-- This is a stack-unsafe function (explained and improved next)
factorial :: Int -> Int
factorial 1 = 1                       -- base case
factorial x = x * (factorial (x - 1)) -- recursive case

factorial 3
-- reduces via a graph reduction...
3 * (factorial (3 - 1))
3 * (factorial 2)
3 * 2 * (factorial (2 - 1))
3 * 2 * (factorial 1)
3 * 2 * 1
6 * 1
6
``````

### Stack-Safe

The above Purescript example illustrates a problem that comes with writing loops this way: stack overflows. Thus, when one says "this function is `stack-safe`", they mean that calling the function will not risk the possibility of a stack overflow runtime error being produced. One usually prevents this risk via tail-call optimization (which usually converts the recursive loop back into an OO loop) or trampolining (when tail-call optimization isn't possible)

Thus, one will usually write recursive functions in this manner. Rather than using recursion to calculate the value by creating a 'stack' of `*` operations (as done above), one will pass into the function an additional argument that acts as the accumulated value. The necessary state change / calculation is done and its result is passed in as the new accumulated value in the next iteration of the recursive function call:

``````factorial :: Int -> Int
factorial n = factorial' n 1

factorial' :: StartingInt -> AccumulatedInt -> AccumulatedInt
factorial' 1 finalResult = finalResult
factorial' amountRemaining accumulatedSoFar =                             {-
-- This is the general idea being done in the single line of code
-- after this comment
let
oneLess = amountRemaining - 1
nextAccumulatedValue = accumulatedSoFar * amountRemaining
in
factorial' oneLess nextAccumulatedValue                               -}
factorial' (amountRemaining - 1) (amountRemaining * accumulatedSoFar)

factorial 4
-- reduces via a graph reduction...
factorial' 4 1
factorial' 3 4
factorial' 2 12
factorial' 1 24
24
``````

In some cases, one will need to write more complex code to get the desired performance using a combination of defunctionalization and continuation-passing style (CPS). This is covered in more detail in the `Design Patterns/Defunctionalization.md` file.

## For ... Break If

``````// findFirst
var findFirst = (array, condition) => {
var length = list.length();
for (var i = 0; i < length; i++) {
var value = list[i]
if (condition(value)) {
return value;
}
}
return null;
}
findFirst([0, 1, 2], (i) => i == 1);
``````
``````-- linked list
data List a
= Nil             -- end of the list
| Cons a (List a) -- head of a linked list & rest of list

data Maybe a
= Nothing   -- could not find a value of type A
| Just a    -- found a value of type A

findFirst :: forall a. List a -> (a -> Boolean) -> Maybe a
findFirst list condition = findFirst' list condition Nothing

findFirst' :: forall a. List a -> (a -> Boolean) -> Maybe a -> Maybe a
findFirst' Nil condition notFound = notFound
findFirst' tail condition theA
findFirst' (Cons head tail) condition Nothing =
in findFirst' tail condition foundOrNot

findFirst (Cons 0 (Cons 1 (Cons 2 Nil))) (\el -> el == 1)
-- reduces via a graph reduction...
findFirst' (Cons 0 (Cons 1 (Cons 2 Nil))) (\el -> el == 1) Nothing
findFirst'         (Cons 1 (Cons 2 Nil))  (\el -> el == 1) Nothing
findFirst'                 (Cons 2 Nil)   (\el -> el == 1) (Just 1)
findFirst'                         Nil    (\el -> el == 1) (Just 1)
Just 1
``````

### Short-Circuiting

The above Purescript example illustrates another problem with writing loops this way: `short-circuiting`. There are times when we wish to break out of a recursion-based loop early, such as when we have found the first element of a collection. In the above example, the function does not short-circuit, so it continues to iterate through the list even after it has found the element, leading to wasted CPU time and work.

To make the function above short-circuit, we would rewrite the function to this:

``````-- linked list
data List a
= Nil             -- end of the list
| Cons a (List a) -- head of a linked list & rest of list

data Maybe a
= Nothing   -- could not find a value of type A
| Just a    -- found a value of type A

findFirst :: forall a. List a -> (a -> Boolean) -> Maybe a
findFirst Nil condition = Nothing
findFirst (Cons head tail) condition =
else findFirst' tail condition

findFirst (Cons 0 (Cons 1 (Cons 2 Nil))) (\el -> el == 1)
-- reduces via a graph reduction...
findFirst         (Cons 1 (Cons 2 Nil))  (\el -> el == 1)
Just 1
``````

## Other Loops

The following Purescript examples are very crude ways of mimicking the following loops. More appropriate examples would require explaining and using type classes like `Foldable`, `Unfoldable`, and `Monad` (intermediate FP concepts). Thus, take these examples with a grain of salt.

### While

``````while (condition == true) {
if (shouldStop()) {
condition = false
} else {
doSomething();
}
}
``````
``````data Unit = Unit

whileLoop :: Boolean -> (Unit -> Boolean) -> (Unit -> Unit) -> Unit
whileLoop false _ _ = -- body
whileLoop true shouldStop doSomething =
-- `doSomething unit` is called in here somewhere
-- at the end of the function's body, it will call
whileLoop (shouldStop unit) shouldStop doSomething
``````

### For `value` in `collection`

``````// length
var count = 0;
for (value in list) {
count += 1;
}
``````
``````data List a
= Nil
| Cons a (List a)

length :: forall a. List a -> Int -> Int
length Nil totalCount = totalCount
length (Cons head tail) currentCount =
length tail (currentCount  + 1)
``````