Recursion:

Recursion is functional approach for looping, the problem with looping in procedural programming is that we need to read the loop to be able to reason about it (we can't apply equational reasoning for non FP). Reasoning for-loop can be easy to the extent that it is very straight-forward and can be written pretty simply and it doesn’t take a lot of mental processing power.

To be able to take the advantage of FP and apply FP principles where looping is necessary we need to use recursion, so it is a very handy tool and sometimes the only practical solution at hand, So it good to get familiarised with recursion.

Having a recursive definition for a given problem is an optimal approach in order to write a recursive function for it, as a programmer our job is to primarily understand the the problem before writing the code. Having a clear definition of a recursion is crucial for equational reasoning.

two major techniques used in recursion are iterative sub-problem, divide and conquer

Let's understand with the example given below:

The solution for the given problem is 'how many vowels are in a string'?, Now let's have a recursive definition for the given problem statement before we start coding.
(Note: we can have multiple definitions of recursion for a given problem).

Reducing the problem set, for any given string let us assume we have n characters, perform operation on individual character and make the string length n-1 characters, by reoccurring this operation until we reach the nth character of the string.

Every recursive solution has to have at a minimum of a base condition. The base determines the halting of recursion.

function isVowel(char) {
    return ['a','e','i','o','u'].includes(char);
}
// Procedural
function countVowels(str, count=0){
    if(str.length>0){
        return isVowel(str.slice(0,1))?countVowels(str.slice(1),count+1):countVowels(str.slice(1),count)
    }
    return count;
}

// Functional
function countVowels(str, count = 0) {
    if(str.length === 0) return count;
    return countVowels(str.slice(1), isVowel(str.slice(0,1))?count+1:count)
}

function coutVowels(str) {
    var first = (isVowel(str[0]) ? 1 : 0);
    if(str.length <=1) return first;
    return first + countVowels(str.slice(1));
}

function dc(str) {
    if(str[0] === str[str.length-1]) return true;
    return false;
}

function isPalindrome(str, res = true) {
    if(str.length <= 1 || res === false) return res;
    return isPalindrome(str.slice(1,-1), dc(str));
}

Recursion & Stack Frames:

In practice we often don't see recursion landing in the code-base one of the main reason for this is recursion compounds stack frames, when ever a function invokes another function at that moment everything that was currently happening in that function needs to get saved and a new stack frame is created for the function call, so that the stuff happening in the other function doest interfere with the HOF. If this keeps happening we will exceed the memory range for call stack.

Optimising Recursion With Proper Tail Calls:

when a function ends by return of calling another function then the latter function does not need to return to its caller. As a consequence, the stack frame of the consequent HOF need not be maintained over the call stack, so it remains consistent. This kind of call is named tail call. With proper tail calls, we can make function calls without growing the call stack. Proper tail call recursion is a memory optimisation it is not necessarily a performance optimisation.

Often when the return of a function has some computation along with the call, we need to think in terms of where else can wee do that computation so that we don't need to keep track of the result of that computation in the current stack and return just a tail call. We can see this in the below examples.

Note: PTC works only on strict mode.

"use strict";
function countVowelsWithPTC(str, count = 0) {
    if(str.length === 0) return count;
    return countVowels(str.slice(1), isVowel(str.slice(0,1))?count+1:count)
}

function coutVowels(str) {
    var first = (isVowel(str[0]) ? 1 : 0);
    if(str.length <=1) return first;
    return first + countVowels(str.slice(1));
}

In the above two functions contVowels is not optimised as the return addition is performed after the function completes, what if there was no more work to do when the return statement is compiled like in the countVowelsWithPTC then the current call stack frame is not needed anymore.

Range Errors in Recursion:

with Proper tails calls we can avoid 'range error: out of memory' by keeping the stack size remain consistent. But on a side note, we really do not run out of memory, if we actually run out of memory then our web app crashes or our system reboots.

Modern browsers actually implement a mechanism to keep a check on stack and if the stack depth keeps increasing then the browser will give range error and stop such function execution.

Recursion alternatives CPS and Trampolines:

Continuous Passing Style:

function countVowels(str, count = v => v){
    var first = isVowel(str[0]) ? 1 : 0;
    if(str.length <=1) return count(first);
    return countVowels(str.slice(1), function(v){
        return cont(first + v)
    })
}

Data Structure Operations:

Operations that can be performed across a single discrete value can be adopted across the collection of values.

Functor - Map transformation:

If the above design pattern is applied with a mapper function over the given data structure, then such types are referred to as functors.

Functor is any data type over which the values in it can be mapped with a map like method defined for it, A map magically applies the given function over the functor and returns a new functor, It always produces transformed values but the same data structure. Functor adheres to FP principles so it is pure and has no mutation. Arrays in JS are inbuilt functors as they have map method built in them.

Note: List operations are not only limited to Arrays as we see in javascript, the functional programming concept of doing operations over lists spans across all general data structures.

function dataContext (data) {
    return { just: data }
}

function fmap(mapper, functor){
    let newFunctor = [];
    for (let elm of functor){
        newFunctor.push(mapper(elm));
    }
    return newFunctor;
}

fmap(dataContext, ['alice', 'bob'])

Filter Transformation:

Filter as the name suggests, filters the collection of values based on the condition and returns the same data structure with filtered values.

function isLoggedIn(user) {
    return user.session != null;
}

function filter(predicate, arr){
    let newList = [];
    for (let elm of arr) {
        if(predicate(elm)){
            newList.push(elm);
        }
    }
    return newList;
}

filter(isLoggedIn, [
{id: 1, session: "a1"},
{id: 2},
{id: 3, session: "b2"}
])

Reduce:

Reduce combines values of a data structure, It has the accumulator (We need to set an initial value to the accumulator) which is the current state of reduction and then the individual value of the current iteration an operation is performed with the accumulator and the current value to give the next value which is stored in next iterations accumulator.

We generally think of reduction being used in operations like adding or dividing over the elements of a list but in contrary reduction is a very general concept. The concept of reducing lists into a value is true even if the reduced value can be another list it does not need to be a primitive value only.

function convertToObject(record, [key,value]) {
    return { ...record, [key]: value };
}

function reduce(reducer, accumulator, arr) {
    var ret = initialVal;
    for (let elem of arr) {
        ret = reducer(ret, elem)
    }
    return ret;
}

reduce(convertToObject, {}, [
    ["name", "alice"],
    ["age", 29],
    ["isDev", true]
])

An important thing to note here is both map and filter functions are unary and the reducer function is binary.

By equational reasoning any function that takes one input can be reasoned with map or filter and any function which takes two inputs and produce one output can be reasoned with reduce.

function add1(v) {return v + 1};

function mul2(v) {return v * 2};

function div3(v) {return v / 3};

function identity(value) {
    return value;
}

function composeTwo(fn2, fn1) {
    console.log("called",fn2,fn1)
    return function composed(v){
        return fn2(fn1(v));
    }
}

var f = [div3, mul2, add1].reduce(composeTwo,identity)

console.log(f(8))

function compose(...fns){
    return function composed(v){
        return fns.reduceRight(function invoke(val, fn){
            return fn(val)
        },v)
    }
}


var f = compose(div3,mul2,add1)
console.log(f(8))