A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

Chapter 12

These are the solutions to the exercises found in the section ​Exercises​.

1. The problem here is the function recursively calls itself twice each time it runs. Let’s make it so that it only calls itself once each time:

   function addUntil100(array) {
     if (array.length === 0) { return 0; }
   
     const sumOfRemainingNumbers = addUntil100(array.slice(1));
   
     if (array[0] + sumOfRemainingNumbers > 100) {
       return sumOfRemainingNumbers;
     } else {
       return array[0] + sumOfRemainingNumbers;
     }
   }

2. Here is the memoized version:

   function golomb(n, memo = {}) {
     if (n === 1) { return 1; }
   
     if (!memo[n]) {
       memo[n] = 1 + golomb(n - golomb(golomb(n - 1, memo), memo), memo);
     }
   
     return memo[n];
   }

3. To accomplish ...