question regarding max value in an array with recursion in JavaScript

Question

Currently, I was able to get the following function to retreive the max value from an array through recursion

const max = ([a,...rest]) => !rest.length || a > max(rest) ? a : max(rest);

console.log(max([-3,3,19,61,99,22,55])); // 99 
console.log(max([32,0,9,87,73])); // 87 
console.log(max([1,6,8])); // 8

However, when I try to refactor it with an extra parameter "b" through destructuring, the whole function just won't work properly anymore.

const max = ([a,b,...rest]) => !rest.length || a > b ? a : max([b,...rest]);

console.log(max([-3,3,19,61,99,22,55])); // 99 
console.log(max([32,0,9,87,73])); // 32 
console.log(max([1,6,8])); // 6

Can someone kindly explain what I am doing wrong or point me in the right direction. I am new to recursion and programming so any help will be greatly appreciated :)

UPDATE:

Took me awhile to figure it out, but here is the recursive solution with destructuring:

const max = ([a,b,...rest]) => !rest.length && !b ? a : max([b < a ? a : b,...rest]);

if the length of "rest" is equal to "0" and "b" doesn't exists then return "a"

!rest.length && !b ? a

else, invoke "max" recursively

: max([b < a ? a : b,...rest]);

for the 1st argument, if "b is less than "a" then return "a" else return "b"
for the 2nd argument, we'll simply "spread" in "rest"

On first glance, you are returning a when !rest.length is true (ie: a and b are the only elements left in your array), but b might be larger than a in this case. Also, you are returning a if a > b, and then don't do any more recursive calls, so for [32, 0, ...], the 32 is bigger than 0, so you straight away return 32 without checking the rest of the array — Nick Parsons
– Nick Parsons, Commented Mar 15, 2022 at 22:37
In the first case, comparison is done between a and rest of elements after it a > max(rest). So it will recursively compare all. But in the second case comparison is between just a and b a > b. So, whenever such a case occurs code execution will finish. In 2nd method, 1st example 99 > 22 first case when a > b and hence luckily right answer, 2nd example 32 > 0 (a > b) found in 1st comparison only and hence wrong answer, 3rd example in 2nd loop params are[6, 8, ...[]] and hence due to rest.length check 6 is returned and comparison isn't even done as length check is done first. — gyan roy
– gyan roy, Commented Mar 15, 2022 at 22:47

Scott Sauyet · Accepted Answer · 2022-03-16 02:53:09Z

You are absolutely right to want to fix the initial recursive version. calling max (rest) twice, and doing it recursively for each subsequently smaller list means that you're calling max 2ⁿ times, where n is the length of the input. (It's more complex that that, varying by whether n is even or odd, but it still grows at that rate.)

So you do need to fix this. But your attempt has several fatal flaws, as already reported in the comments. First of all, it's quite possible that you're destructuring more arguments than your list has elements. (What would b be in max ([42])?) Second, when you get down to two elements (!rest .length), you always return the first one. What if the second is larger?

My approach would probably be to add a helper function that takes the maximum of two elements, and then use that to write the main function. It might look like this:

const max2 = (a, b) => a > b ? a : b

const max = ([a, ...rest]) => 
  rest .length == 0 ? a : max2 (a, max (rest)) 

console.log (max ([-3, 3, 19, 61, 99, 22, 55])); // 99 
console.log (max ([32, 0, 9, 87, 73])); // 87
console.log (max ([1, 6, 8])); // 8

Of course, instead of a helper function, we could always use Math .max, but that smacks of cheating.

If you have a strong aversion to helper functions, you can use a defaulted parameter instead. But I think this code is more convoluted, and not very helpful:

const max = ([a, ...rest], b = rest.length ? max (rest) : -Infinity) => 
  rest .length == 0 ? a : a > b ? a : b

In here we use -Infinity for a value guaranteed to be no larger than any other value. That might be useful in the snippet version too. Right now if you pass max an empty array, it returns undefined. If we wanted it to return -Infinity instead, then we could default a to -Infinity:

const max = ([a = -Infinity, ...rest], b = rest.length ? max (rest) : -Infinity) => 
  rest .length == 0 ? a : a > b ? a : b 


max ([]) //=> -Infinity

Collectives™ on Stack Overflow

question regarding max value in an array with recursion in JavaScript

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related