Recursion - Exercise

Contact Us or call 1-877-932-8228
Recursion - Exercise

Recursion

Duration: 20 to 30 minutes.

In this exercise, you will create a function that finds the maximum value among the elements of an integer array.

  1. Open AdvancedFunctions/Exercises/findMax.html for editing.
  2. Where indicated in the for loop inside the window.onload handler: generate a random number, add it to the array a, and write the number to the screen.
  3. Write the body of function FindMax which, when passed an array of integers, should return the greatest value in the array. Write the function using recursion, per the following strategy:
    • If the array parameter arr has one element, return that element as the max.
    • Otherwise, the max value is either the first element or the maximum of the remaining part of the array.
    • You can use arr.slice(1) to get the "all but the first element" portion of the array.
  4. Test your solution in a browser.

Solution:

AdvancedFunctions/Solutions/findMax.html
<!DOCTYPE html>
<html>
<head>
	<meta charset="utf-8">
	<title>Find Max</title>
	<style>
		#arrayDisplay {
			font-size:24px;
			margin-bottom:5px;
		}
		button {
			padding:2px 5px;
			font-size:20px;
		}
	</style>
	<script>
		function findMax(arr) {
			if (arr.length == 1) {
				return arr[0];
			} else {
				var max1 = arr[0];
				var max2 = findMax(arr.slice(1));
				if (max1 > max2) {
					return max1;
				}
				else  {
					return max2;
				}
			}
		}

		window.onload = function() {
			var a = [];
			var arrayDisplay = document.getElementById('arrayDisplay');
			arrayDisplay.innerHTML = '';
			for(var i=0; i<10; i++) {
				var randomNum = Math.floor((Math.random() * 200) + 1) - 50;
				a.push(randomNum);
				arrayDisplay.innerHTML += a[i];
				if (i < 9) {
					arrayDisplay.innerHTML += ', ';
				}
			}

			var resultDisplay = document.getElementById('resultDisplay');
			document.getElementById('doFindMax').addEventListener('click', function(e) {
				resultDisplay.innerHTML = '';
				resultDisplay.innerHTML = 'The max is: ' + findMax(a);
			}, 'false');
		}
		
	</script>
</head>
<body>
	<h1>Find Max</h1>
	<div id="arrayDisplay"></div>
	<button id="doFindMax">Find Max</button>
	<div id="resultDisplay"></div>
</body>
</html>

Code Explanation

We generate a random number with Math.floor((Math.random() * 200) + 1) - 50 (subtracting "50" to make some of the numbers negative), add the random number to the array with a.push(randomNum), and write the number to the screen with arrayDisplay.innerHTML += a[i].

Our recursive findMax function first checks the length of its array parameter arr, returning the first (and only) element if the length is 1.

If not - that is, if the array has length of at least 2 elements - then the function compares the first element (arr[0]) with the rest (findMax(arr.slice(1))) of the array, with the latter being a recursive call to findMax. The function returns the larger of the two as the maximum value.

Next