Recursion

Welcome to our free Advanced JavaScript Programming tutorial. This tutorial is based on Webucator's Advanced JavaScript Programming course.

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:

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

var result = document.getElementById('result');
var num = parseInt(document.getElementById('num').value);
result.value = factorial(num);
}, 'false');
}

</script>
<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:

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

var result = document.getElementById('result');
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>
<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 `n`th 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:

This tutorial is based on Webucator's Advanced JavaScript Programming Course. We also offer many other JavaScript Training courses. Sign up today to get help from a live instructor.