❮❮ PREV NEXT ❯❯

JAVASCRIPT - RECURSION

Recursion is a technique where a Function calls itself. It might look a little tough. But we will try making it as easy as possible.

Let us understand Recursion using the program to find out the Factorial of a number.

Below is how we calculate the factorial of a number.

Say, we want to calculate the factorial of 3.

3 * 2 * 1 = 6

Similarly, the factorial of 6 is,

6 * 5 * 4 * 3 * 2 * 1 = 720

Below is a program to calculate the factorial of 3 using Recursion.

Example :

<html>
<body>  
<script>

	function fact(x) {
    	if (x == 1) {
        	return 1
    	}    
    	else {
        	return (x * fact(x-1))
    	}
	}        

var n = 3
var f = fact(n)
document.write("The factorial of ", n, " is ", f)
	    
</script>      
</body>
</html>

Output :

The factorial of 3 is 6

In the above code, we are calculating the factorial of 3.

So, we have initialised the value of n with 3.

var n = 3

And called the fact(n) Function, passing the value of n(i.e. 3).

var f = fact(n)

And the execution of fact Function begins.

function fact(x) {
	if (x == 1) {
		return 1
	}
	else {
		return (x * fact(x-1))
	}
}

So, the value of x is 3(That is passed as argument).

Then in the next line, we have checked if the value of x is 1. If so, the method execution stops and 1 is returned.

if (x == 1) {
	return 1
}

Now, since the value of x is 3. We come to the else part and come across the recursive call, where the fact Function calls itself.

else {
	return (x * fact(x-1))
}

But the thing to note is that there is a return statement. A return statement actually means to return the value and finish the Function execution.

But in this case the value will not be returned immediately. Instead, the fact Function calls itself.

And JavaScript, maintains an internal Stack that is hidden from the user.

So, in the return statement, if we substitute the value of x with 3.

return (x * fact(x-1))

It becomes return (3 * fact(2)). And that is kept in the internal stack maintained by JavaScript.

For fact(3), JavaScript keeps a note in stack that the return value is return (3 * fact(2)).And the value of fact(2) is yet to be determined.

Now, fact(2) Function from return (3 * fact(2)) with the new Argument, 2 is called. And the first pass begins.

1st Pass

So, the value of x is 2(That is passed as recursive argument).

And the fact(2)(i.e. After substituting the value of x by 2) Function execution begins with new Argument 2.

function fact(x) {
	if (x == 1) {
		return 1
	}
	else {
		return (x * fact(x-1))
	}
}

Similarly, the control comes to the else statement and the return statement is encountered.

else {
	return (x * fact(x-1))
}

Even in this case JavaScript finds a recursive call to the fact Function.

So, it stores the value in the stack.

So, in the return statement, if we substitute the value of x with 3.

return (x * fact(x-1))

It is return (2 * fact(1)).

Now, fact(1) Function with the new Argument, 1 is called. And the second pass begins.

2nd Pass

So, the value of x is 1(That is passed as recursive argument).

And the fact(1) Function execution begins with new Argument 1.

function fact(x) {
	if (x == 1) {
		return 1
	}
	else {
		return (x * fact(x-1))
	}
}

Now, the control comes to the if statement

if (x == 1) {
	return 1
}

and the return 1 statement is encountered.

Now, JavaScript doesn't find a recursive call to the fact Function.

And the return value for fact(1) is 1.

And now, it is time for JavaScript to Backtrack

i.e. To get the values out of the Stack.

So JavaScript goes to the top element of the stack and takes it out.

And the topmost element is fact(2) with value return (2 * fact(1)). So, it takes out fact(2) and substitutes the value of fact(1) with 1.

And the value of fact(2) becomes,

'fact(2)' -->  'return (2 * fact(1))' -->  return (2*1) --> return 2

So, the value of fact(2) is 2.

So JavaScript goes to the stack again.

And the topmost element is fact(3) with value return (3 * fact(2)). So, it takes out fact(3) and substitutes the value of fact(2) with 2.

And the value of fact(3) becomes,

'fact(3)' -->  'return (3 * fact(2))' -->  return (3*2) --> return 6

So, the value of fact(3) is 6.

Now since, the Stack is empty,

JavaScript returns the value of fact(3) i.e. 6.

And finally, the value is fact(3) is returned.

var f = fact(n)

And the returned value is assigned to f.

And the document.write statement,

document.write("The factorial of ", n, " is ", f)

Prints the output.

The factorial of 3 is 6

Next, let us take the example of Fibonacci Series.

A Fibonacci Series is generated by by adding the previous number of the sequence with the current number to generate the next number in the sequence.

Too much in a line? Let us make in simple.

Let us see the first six numbers of the Fibonacci Series.

0	1	1	2	3	5

Let us understand Fibonacci Series using Recursion.

Example :

<html>
<body>  
<script>

	function fib(n) {
		if(n == 0){
			x = 0
        }    
		else if(n == 1) {
			x = 1
        }    
		else {
			x = fib(n - 1) + fib(n - 2)
		}	
		return x
    }

for (var i = 0; i< 6; i++) {
	document.write(fib(i), "</br>")
}    
	    
</script>      
</body>
</html>

Output :

0
1
1
2
3
5

The explanation is left for the users to understand.

❮❮ PREV NEXT ❯❯