Recursion

Recursion is the function calling itself.

Case

Base case: The condition to stop the loop
Recursive case: Keep self calling the function

function countdown(i){
 console.log(i);
 if (i <= 0) { // Base case
  return 
 }
 return countdown(i-1); // Recursive case
}

Cost

Recursion saving the info needs memory, if your recursion have to execute man times, you will need lots of memory.

However, it can be solved by Tail Recursion.

Call stack with recursion

Example: factorial

function factorial(num) {
  if (num === 1) return 1;
  return num * factorial(num - 1);
}
factorial(4);

Call stack can get very tall which take a lot of memory. It’s a Stackoverflow error.¹

Reference:
Hero Picture

Practice: Sum

Here comes the practice. Figure out the base case of Sum, and convert it to recursion function.

Base case: what’s the simplest part in the array?

function sum(arr){
 let total = 0;
 for (let i = 0; i < arr.length; i++) {
 total += arr[i];
 }
 return total;
}

Did you solve this?
The simplest part in the array is an element of the array or an empty array. By reducing the numbers of element, you can reduce the size of the problem.

Yes, it’s arr[i] in the array.
And pass the reduced size array repeatedly.


function sum(arr) {

  // If the array is empty, return 0
  if (arr.length === 0) return 0

  // otherwise, total sum is the first number plus the sum of the rest number of the array
  return arr[0] + sum(arr.slice(1));

}

sum([1, 2, 3]);

The function call breakdown would be:

sum([1, 2, 3]);

// 1 + sum([2,3])
// 1 + 2 + sum([3])
// 1 + 2 + 3 + sum([])
// 1 + 2 + 3 + 0
// 6

Binary Search

Binary Search can be implemented with recursion function. The base case in Binary Search is an array with one item. The recursive case is a binary search with another half array.

 function binarySearch(target, arr) {
  

  function search(array) {
    let half = Math.ceil(array.length / 2);
    if (array[half] === target) return half;
    else if (target > array[half]) {
      return search(array.slice(half + 1))
    } else if (target < array[half]) {
      return search(array.slice(arr[0], half - 1));

    }

  }

  return search(arr);
}

binarySearch(4, [1, 1, 4, 40]);

Stackoverflow error happens when call stack exceeds due to excessive deep or infinite recursion. ↩︎

Mina Huang