02.-Working-with-Recursion.md

Working with Recursion

One of the functional programming techniques is recursion, in which a function calls itself while it's executing. A function calling itself is calling a function, which makes it a higher order function.

Following the good practices of making pure functions and structure your recursion correctly, recursion can be a good solution for certain types of problems.

The definition of recursion means repeatedly calling a function from within itself, and then iterating until a completion state is reached. Ideally, you return to result without affecting anything outside of the function, and recursion can be a good alternative to a traditional looping structure.

an example of a type of problem that might be best solved with recursion is the classic factorial. To perform a classic factorial operation, you multiply an integer by the previous integer. Then you multiply that product by the next previous integer and you keep on going backwards until you reach 1.

At that point you stop, and you return the result. So for example, to calculate the factorial of three, you take 3 multiplied by 3 minus 1, which is 2. And then multiplied by 2 minus 1, which is 1 and you'd get 6. Similarly, the factorial of six is 6 x 5 x 4 x 3 x 2 x 1, which gives us a result of 720.

Traditional Looping

using for loop

const factor = number => {
  let result = 1;
  for (let count = number; count > 1; count--) {
    result *= count;
  }
  return result;
};
console.log(factor(6)); // 720

using while loop

const factor = number => {
  let result = 1;
  let count = number;
  while(count > 1) {
    result *= count;
    count--
  }
  return result;
};
console.log(factor(6)); // 720

Using Recursion

factorial using recursion

const factorial = number => {
  if (number <= 0) {
    return 1;
  }
  return (number * factorial(number - 1));
}

console.log(factorial(6));

Keep in mind, recursion incurs a high memory price and depending on how deep the recursion goes that can cause an issue for your programs. There's a technique called proper tail calls and they are an option, but in order to use them effectively you have to make your recursive functions a little bit more complex. In addition, JavaScript engines can optimize for proper tail calls in order to avoid the deep memory issues.

When we did console.log(factorial(6)) we were running this code six times and that meant that each one of these was being stacked up in memory and maintained while the first one was running.

That's a lot of memory usage. In some cases it's possible to get around this memory issue with recursive functions by using a technique called proper tail calls. With proper tail calls, your recursive function can rewrite values to the last frame of the memory stack. And you do that by making sure that the recursive call itself is in a tail position in the function. That's done by making sure that that recursive call is returned without any additional calculations.

In order to make factorial optimizable, we might want to create a function and call it const factorialPTC for proper tail call.

const factorialPTC = number => factorIt(number, 1);

const factorIt = (number, accumulator) => {
  if (number <= 1) {
    return accumulator;
  }
  return factorIt(number -1, number * accumulator);
};

console.log(factorialPTC(6));