JavaScript Recursive Function

What is Recursion in JavaScript?

Recursion is a programming technique where a function calls itself to solve a smaller part of the same problem.

Instead of using loops like for or while, recursion keeps calling itself until a condition is met. If no base case is defined, the function will call itself indefinitely, leading to stack overflow.

👉 Simple idea: “Solve a big problem by solving smaller versions of it.”

Recursion Basic Structure

Every recursive function has two main parts:

1. Base Case: A condition that stops the recursion.
2. Recursive Case: A call to the function itself with a modified argument.

If you miss the base case, your program will run forever (infinite recursion).

Recursion without Base Case

Without a base case, the function will keep calling itself indefinitely. This leads to a stack overflow error as the stack cannot hold all the function calls.

All functions in stack creates a frame, nested function creates a new frame inside it. Stack cannot hold all the function calls due to limited memory. This type of error is known as stack overflow.

function recursion(){
  return recursion();  // recursive case
}

Recursion with Base Case

With a base case, the function will stop calling itself when the condition is met. This prevents infinite recursion and stack overflow.

function recursion(n){
  if(n <= 1){ return 1}        // base case
  return n + recursion(n - 1);    // recursive case
}

Calculate Factorial using Recursion

Calculating factorial using recursion is a classic example of how recursion works. In factorial, we multiply a number by all positive integers less than it up to 1.

Base case

The base case for factorial is when the number is less than or equal to 1, in which case the factorial is 1.

Recursive case

The recursive case is when the number is greater than 1, in which case the factorial is the number multiplied by the factorial of the number minus 1.

function factorial(n){
  if(n <= 1){
    return 1;  // base case
  }
  return n * factorial(n - 1); // recursive case
}

Recursive Logic:

When you call factorial(5), it will compute as follows:

1. factorial(5) returns 5 * factorial(4)
2. factorial(4) returns 4 * factorial(3)
3. factorial(3) returns 3 * factorial(2)
4. factorial(2) returns 2 * factorial(1)
5. factorial(1) returns 1 (base case)

Then it will backtrack and compute the final result:

1. factorial(1) returns 1 (base case)
2. factorial(2) returns 2 * 1 = 2
3. factorial(3) returns 3 * 2 = 6
4. factorial(4) returns 4 * 6 = 24
5. factorial(5) returns 5 * 24 = 120

Fibonacci Sequence

Fibonacci Sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1.

The Fibonacci sequence can be calculated using recursion, where each number is the sum of the last two numbers. If last two numbers are 0 and 1, then the next number is 1.

function fibonacci(n){
  if(n <= 1){ return n }                    // base case
  return fibonacci(n - 1) + fibonacci(n - 2); // recursive case
}

Sum of array

To calculate the sum of an array in JavaScript, you can use recursive function, a loop or the reduce() method.

function sumArray(arr, n) {
  if (n <= 0) { return 0; }              // Base case: empty array has sum of 0
  return sumArray(arr, n - 1) + arr[n - 1]; // Recursive case
}

Real World Applications

Recursion is widely used in various real-world applications, including:

1. Tree Traversal: Recursion is commonly used to traverse tree data structures, such as DOM trees in web development.
2. Graph Algorithms: Many graph algorithms, like depth-first search (DFS) and breadth-first search (BFS), can be implemented using recursion.
3. Sorting Algorithms: Recursive algorithms like quicksort and mergesort are efficient sorting techniques.
4. Dynamic Programming: Recursion is often used in dynamic programming to solve problems by breaking them down into smaller subproblems.
5. Backtracking: Recursive backtracking algorithms are used for solving constraint satisfaction problems, such as puzzles and combinatorial problems.

Recursion Vs Loops

Recursion and loops are both used to repeat a block of code, but they have different approaches and use cases.