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

Unnecessary Recursive Calls

Here’s a recursive function that finds the greatest number from an array:

def max(array)

  # Base case - if the array has only one element, it is
  # by definition the greatest number:

  return array[0] if array.length == 1

  # Compare the first element with the greatest element
  # from the remainder of the array. If the first element
  # is greater, return it as the greatest number:
  if array[0] > max(array[1, array.length - 1])
    return array[0]

  # Otherwise, return the greatest number from the remainder of the array:
  else
    return max(array[1, array.length - 1])
  end
end

The essence of each recursive call is the comparison of a single number (array[0]) to the ...