A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Chapter 12

These are the solutions to the exercises found in the section, ​Exercises​. The solutions provided here are in Ruby, but you can find the solutions in JavaScript and Python in the code download.^[12]

1. The problem here is that we have two recursive calls to the function within itself. We can easily reduce it to one:

   def add_until_100(array)
     return 0 if array.length == 0
     sum_of_remaining_numbers = add_until_100(array[1, array.length - 1])
     if array[0] + sum_of_remaining_numbers > 100
       return sum_of_remaining_numbers
     else
       return array[0] + sum_of_remaining_numbers
     end
   end

2. Here is the memoized version:

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