Recursion

What is Recursion ?

A process (a function in our case) which calls itself.

It's everywhere: JSON.parse, JSON.stringify

The Call Stack

1. Any time a function is invoked it is placed (pushed) on top of the call stack.
2. When Javascript sees the return keyword, or when the function ends, the compiler will remove (pop)

The essential parts of a recursive function => Base Case and Different input

Base Case

The condition when the recursion ends => this is the most important concept to understand.

CountDown.js

function CountDown(num) {
  // this is our base case
  if (num <= 0) {
    console.log('all done!!!');
    return;
  }

  console.log(num);
  num--;
  CountDown(num);
}

Where things go wrong?

Common problems that arrives when you writing recursive solutions

1. when base case is wrong or you don't have a base case => So you should have a base case, without it you put your function inside an infinite loop And you will get this error => maximum call stack size exceeded

2. Forgetting to return or return the wrong thing. => in this case as well you'll put your recursive function inside infinite loop.

Maximum Call Stack Size Exceeded === Stack Overflow :)))

Introduction of a Design Pattern that commonly used with Recursion => Helper method Recursion

So far, all the recursive function we've written are single stand alone functions, like factorial it is recursive itself, we call factorial from outside of the function, and factorial itself calls factorial.

with helper method recursion, it's a little bit different

with helper method recursion we have two functions. we have outer function and inside we have recursive function

function outer(input) {
  var outerScopedVariable = []

  function helper(helperInput) {
    // modify the outerScopedVariable
    helper(helperInput--)
  }

  helper(input)

  return outerScopedVariable;
}

this is commonly done when we need to compile something like an array or a list of data.

Good example

Let's try to collect all of the odd values in an array!

function collectOddValues(arr) {
  let result = [];

  function helper(helperInput) {
    if (helperInput.length === 0) return;

    if (helperInput[0] % 2 !== 0) {
      result.push(helperInput[0])
    }

    helper(helperInput.slice(1))
  }

  helper(arr)

  return result
}