Recursion

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

Recursion

Recursion in JavaScript is, like in any functional programming language, the process of a function calling itself. Many real-life phenomena lend themselves to recursion. Consider the process of generating factorial numbers: x! ("x factorial") is defined as x * (x-1) * (x-2) ... * 1. For example:

4! = 4 * 3 * 2 * 1 = 24

3! = 3 * 2 * 1 = 6

2! = 2 * 1 = 6

1! = 1 = 1

0! = 1

Note that, by definition, 0! = 1.

The astute observer will quickly recognize that it is always the case that

x! = x * (x-1)!

that is, we can find the factorial for any number by multiplying the number itself by the factorial of the number one less, until we reach 0 (and, thus, stop the process.)

The example above illustrates the two things we need to employ recursion: a way to make a larger problem a little bit smaller, and a way to know when to stop. Let's look at a code example to see how this works.

Code Sample:

AdvancedFunctions/Demos/recursionFactorial.html
<!DOCTYPE html>
<html>
<head>
	<meta charset="utf-8">
	<title>Recursion - Factorial</title>
	<style>
		input {
			padding:4px;
			width:57px;
		}
		input, button {
			padding:2px 5px;
			font-size:20px;
		}
	</style>
	<script>
		function factorial(x) {
			if (x == 0) {
				return 1;
			} else {		
				return (x * factorial(x-1));
			}
		}

		window.onload = function() {
			var result = document.getElementById('result');
			document.getElementById('doFactorial').addEventListener('click', function(e) {
				var num = parseInt(document.getElementById('num').value);
				result.value = factorial(num);
			}, 'false');
		}
		
	</script>
</head>
<body>
	<h1>Recursion - Factorial</h1>
	<input type="text" id="num">
	<button id="doFactorial">!</button>
	<input type="text" id="result">
</body>
</html>

Code Explanation

Our page listens for clicks on the #doFactorial button, getting the value of the left textfield as num and setting the value of the right textfield to factorial(num).

Function factorial is defined to use recursion: if the argument x passed to it is 0, then we return 1. If not (and we assume that only integers greater than 0 are passed to our function), then the function calls itself, passing x-1 as the parameter. Thus:

factorial(3) =

3 * factorial(2) =

3 * 2 * factorial(1) =

3 * 2 * 1 * factorial(0) =

3 * 2 * 1 * 1 =

6

Another example is the Fibonacci sequence, a list (sequence) of numbers defined as follows:

  • The first number is always 1.
  • The second number is always 1.
  • Each successive number is defined as the sum of the previous two numbers.

Thus the first six number in the Fibonacci sequence are:

1, 1, 2, 3, 5, 8

Following is an example in JavaScript of a recursive function to generate the first n numbers of the Fibonacci sequence:

Code Sample:

AdvancedFunctions/Demos/recursionFibonacci.html
<!DOCTYPE html>
<html>
<head>
	<meta charset="utf-8">
	<title>Recursion - Fibonacci</title>
	<style>
		input {
			padding:4px;
			width:57px;
		}
		input, button {
			padding:2px 5px;
			font-size:20px;
		}
	</style>
	<script>
		function fibonacci(n) {
			if (n == 1 || n == 2) {
				return 1;
			} else {
				return (fibonacci(n-1) + fibonacci(n-2));
			}
		}

		window.onload = function() {
			var result = document.getElementById('result');
			document.getElementById('doFibonacci').addEventListener('click', function(e) {
				var num = parseInt(document.getElementById('num').value);
				result.innerHTML = '';
				for(var i=1;i<=num;i++) {
					result.innerHTML += fibonacci(i);
					if (i < num) {
						result.innerHTML += ', ';
					}
				}
			}, 'false');
		}
		
	</script>
</head>
<body>
	<h1>Recursion - Fibonacci</h1>
	<input type="text" id="num">
	<button id="doFibonacci">Go</button>
	<div id="result"></div>
</body>
</html>

Code Explanation

Our page listens for clicks on the #doFibonacci button, getting the value of the left textfield as num and setting, via a for loop, the innerHTML of the #result div to the first num elements of the Fibonacci sequence.

Function Fibonacci returns the nth number of the Fibonacci sequence. If the parameter n is 1 or 2, then the function returns 1; if not - that is, if n is greater than 2 - then the function finds the value recursively, returning:

Fibonacci(n-1) + Fibonacci(n-2)

We'll ask you to try out using recursion in the next exercise:

Next