I am trying to use recursion to find the maximum value in an array in JavaScript. I created the function, but cannot figure out how to do it recursively.
function Max(a) {
var a = [2,3,5];
return Math.max.apply(Math, a);
}
I am trying to use recursion to find the maximum value in an array in JavaScript. I created the function, but cannot figure out how to do it recursively.
function Max(a) {
var a = [2,3,5];
return Math.max.apply(Math, a);
}
- 4 Recursion is the function calling itself. If the function gets passed the array of values, what is it that you want to pass to the inner function call? – Felix Kling Commented Nov 5, 2015 at 0:46
- 1 Hint: max(a,b,c) = max(max(a,b),c). – mpen Commented Nov 5, 2015 at 0:58
- stackoverflow./questions/1379553/… – Tom Netzband Commented Nov 5, 2015 at 1:00
- 1 Why are the array values set inside your function? – nnnnnn Commented Nov 5, 2015 at 1:01
- 1 The Math.max function does the recursive (or iterative?) part "under the hood" in the browser's core code. So if your goal/assignment is to write an "iterative function" you should maybe look here (wrong language, right idea). – James Commented Nov 5, 2015 at 1:06
11 Answers
Reset to default 2let max = (list) => {
// Returns first number if list length is 1
if (list.length === 1) return list[0]
// Returns the greater number between the first 2 numbers in an array
if (list.length === 2) return (list[0] > list[1]) ? list[0] : list[1]
// If array length is 3+ (Read Below)
const subMax = max(list.slice(1));
return (list[0] > subMax) ? list[0] : subMax;
}
// Example
max([5,5,5,8,6,7,4,7])
It is important to understand how the 'Call Stack' works for recursions.
In the example above, since the array length is over 3 the first line to be called is the
const subMax = max(list.slice(1));
All this line does is take out the first item in the array and recalls the function with the shorter array as its argument. This continues until the arrays length is 2 then returns the greater of the 2. Then the function can plete all its previous partially pleted states.
ES6 syntax makes this really concise.
const findMax = arr => {
if (!Array.isArray(arr)) throw 'Not an array'
if (arr.length === 0) return undefined
const [head, ...tail] = arr
if (arr.length === 1) return head
return head > findMax(tail)
? head
: findMax(tail)
}
Here is an example of a recursive function that takes an array of numbers and pares the first two, removes the lesser, and then calls itself again on the given array minus the removed number.
function max(numArray)
{
// copy the given array
nums = numArray.slice();
// base case: if we're at the last number, return it
if (nums.length == 1) { return nums[0]; }
// check the first two numbers in the array and remove the lesser
if (nums[0] < nums[1]) { nums.splice(0,1); }
else { nums.splice(1,1); }
// with one less number in the array, call the same function
return max(nums);
}
Here's a jsfiddle: https://jsfiddle/t3q5sm1g/1/
This is actually one of the questions I’ve asked candidates to a software position: Find the maximum number in a jagged array. Each element of the array can be a number or an array of other numbers on indefinite number of levels, like this:
var ar = [2, 4, 10, [12, 4, [100, 99], 4], [3, 2, 99], 0];
And now, just for fun and to keep this post short, I will include two solutions to the question. The first solution uses recursion while the second solution uses a stack. As a matter of fact all these problems with recursion can be also solved by using the stack approach.
Solution I: Find maximum using recursion
// Use recursion to find the maximum numeric value in an array of arrays
function findMax1(ar)
{
var max = -Infinity;
// Cycle through all the elements of the array
for(var i = 0; i < ar.length; i++)
{
var el = ar[i];
// If an element is of type array then invoke the same function
// to find out the maximum element of that subarray
if ( Array.isArray(el) )
{
el = findMax1( el );
}
if ( el > max )
{
max = el;
}
}
return max;
}
Solution II: Find maximum using a stack
// Use a stack to find the maximum numeric value in an array of arrays
function findMax2(arElements)
{
var max = -Infinity;
// This is the stack on which will put the first array and then
// all the other sub-arrays that we find as we traverse an array
var arrays = [];
arrays.push(arElements);
// Loop as long as are arrays added to the stack for processing
while(arrays.length > 0)
{
// Extract an array from the stack
ar = arrays.pop();
// ... and loop through its elements
for(var i = 0; i < ar.length; i++)
{
var el = ar[i];
// If an element is of type array, we'll add it to stack
// to be processed later
if ( Array.isArray(el) )
{
arrays.push(el);
continue;
}
if ( el > max )
{
max = el;
}
}
}
return max;
}
Feel free to optimize the above code. You can also find this code as a gist on github.
function max(array) {
if (array.length === 1) { // Step1: set up your base case
return array[0]
} else {
return Math.max(array.shift(), max(array); // Step2: rec case
}
}
Each time the recursive case is called it gets it closer to the base case.
Math.max accepts two numbers, then pares them, then returns the higher out of the two.
Each time you call array.shift() you are popping off the first element in the array from the array, so the second argument in the recursive call is the array shortened by one.
When array.length is down to just one element, return that element and watch the stack unfold.
Try this:
const biggestElement = list => {
if (list.length == 1)
return list[0];
if (list[0] > list[1])
list[1] = list[0];
list = list.splice(1);
return biggestElement(list);
}
function recursiveMaxNumber(items){
if(items.length === 1){
return items[0] //Base-case reached
}
else{
if(items[0]>=items[items.length-1]){
items.pop() //remove the last item in the array
return recursiveMaxNumber(items)
}
else{
return recursiveMaxNumber(items.slice(1)) //remove the first item in the array
}
}
}
console.log(recursiveMaxNumber([2,22,3,3,4,44,33]))Though its not an efficient way below is my try,
function max(a, b) {
return a > b ? a : b
}
function findMaxOfArrayRecursion(arr) {
if (arr.length == 1) {
return arr[0]
}
return max(arr[0], findMaxOfArrayRecursion(arr.slice(1)))
}
Basically we are assuming the first array element to be the maximum & paring it with other elements in a recursive way.
Adding an efficient non-recursive approach as well just for reference,
Math.max(...arr)
const getMax = (arr) => {
// base case
if(arr.length === 0) return -Infinity;
if(arr.length === 1) return arr[0];
// recursive case
return Math.max(arr[0], getMax(arr.slice(1)));
}
getMax([5, 2, 11, 9]) //11
function max(arr) {
if (arr.length > 0) {
return arr[arr.length - 1] > max(arr.slice(0, -1))
? arr[arr.length - 1]
: max(arr.slice(0, -1));
}
return 0;
}
max([3, 2, 1, 7, 5]) //7
or with a bit reacher naming:
function max(arr) {
if (arr.length > 0) {
const currentValue = arr[arr.length - 1];
const nextValue = max(arr.slice(0, -1));
return currentValue > nextValue ? currentValue : nextValue;
}
return 0;
}
I just want to add another possibility without using slice/splice method, but still simple:
function searcMaxValue(numbers, max = 0, index = 0) {
let actual = numbers[index] | 0;
if (actual > max) max = actual;
if (index >= numbers.length - 1) return max;
return searcMaxValue(numbers, max, ++index);
}