Recursion Examples JavaScript

What is recursion?

It is a problem-solving technique that relies on solutions for smaller instances of the same problem.
If we have to get more technical, we can say recursion is when a function calls itself. Let’s see how to create a recursion function with examples in javascript

Why would we need it?

Recursion is a great technique to simplify our solution. If you find yourself breaking down your problem into smaller versions of the sample problem, recursion is very useful.

Analogy

There is a college in your neighborhood, you go to the principal and ask how many students are there in your college. The principal replies the total number of students is equal to the total number of students under professorA who is the head of science and professorB who is the head of commerce. When the two professors are asked the same quession. ProfessorA replies the total number of student in science is equal to the total number of students under TeacherA + TeahcerB, similarly professorB replies the total number of students in commerce is equal to the total number of students under TeacherC + TeahcerD.

This is the lowest level to which the problem can be broken down. Now, the teachers count the number of students and report back to the professor. The professors report the total back to the principal. The principal then responds with the total number of students in the college. The problem has always been finding the number of students but in each level problem is smaller.

Few points about recursion:

Before we solving the fibonacci and factorial problems with recursion. You learn few points about recursion:

1. Every recursive solution needs to have a base case, a base case is nothing but a condition to terminate the recursion. If you don’t have the base case you will have an infinte loop which can crash your program.
2. Recursion might simplify solving a problem but it does not always translate to a faster solution. A recursive solution may be far worse compared to an iterative solution.
3. It is a topic that is not the msot straight forward to understand. Do not give up if you struggle with the concept.

Examples

Fibonacci Sequence:

Problem: In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. The first two numbers in the sequence are 0 and 1.
Ex : 0, 1, 1, 2, 3, 5, 8,…

Solution:

function fibonacci(n){
const fib = [0,1];
for(let i=2;i<n;i++){
fib[i]=fib[i-1]+fib[i-2]
}
return fib
}

document.write(fibonacci(8))

Output:

Steps:

1. First, we created a function called “fibonacci()” and it has one parameter, which denotes how many number in the sequences we have to display.
2. We know the first two numbers are 0 and 1. So, Inside the function, we created a constant called “fib” and initailize with an array of two numbers o & 1.
3. Then we need to populate the remaining elements from the third element till n while satisfying the condition that every number should be the sum of previous two numbers. To populate the remaining elements, we use for loop starts from 2 and we iterate till we have n elements in array.
4. Inside the loop, we adding fib[i] to previous two numbers, so fib[i] – fib[i-1] + fib[i-2]. If n is equal to 3, fib of three would be fib[2]+ fib[1]. Once the for loop exits, we return the array.
5. That is our implementation of the fibonacci sequence in Javascript.
6. See, the output our sequence is successfully executed.