RECURSION

Recursion is a programming technique where a function calls itself in order to solve a problem. It allows developers to break down a problem into smaller subproblems and solve them one by one. A key aspect of recursion is the concept of a base case and a recursive case, which determines when the function should stop calling itself and what input should be used for the next recursive call. When used correctly, recursion can lead to elegant and efficient code, but it can also cause infinite loops if the base case is not defined properly.

Recursion is a powerful programming concept that allows developers to write elegant and efficient code. In this blog post, we will explore recursion from the basics to advanced techniques, with 10 examples to illustrate the key concepts.

1. Basic Recursion: The first example of recursion is the classic factorial function. The factorial of a number n is the product of all positive integers less than or equal to n.

function factorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n-1);
  }
}

A. Base Case: It is important to have a base case in recursion, as it prevents the function from running indefinitely. In the above example, the base case is when n == 0, and the function returns 1.

B. Recursive Case: The recursive case is when the function calls itself with a different input. In the factorial example, the recursive case is when the function calls itself with the input n-1.

C. Tail Recursion: Tail recursion is a special case of recursion where the recursive call is the last thing that happens in the function.

function tailFactorial(n, accumulator=1) {
    if (n === 0) {
        return accumulator;
    } else {
        return tailFactorial(n-1, n*accumulator);
    }
}

2. Memoization: Memoization is a technique that can be used to optimize recursive functions. Memoization stores the results of previous function calls, so that the function does not need to recompute the same values.

function fibonacci(n, memo = {}) {
    if (n === 0) {
        return 0;
    } else if (n === 1) {
        return 1;
    } else if (n in memo) {
        return memo[n];
    } else {
        memo[n] = fibonacci(n-1) + fibonacci(n-2);
        return memo[n];
    }
}

3. Divide and Conquer: Divide and conquer is a technique that can be used to solve problems recursively by breaking them down into smaller sub problems.

function binarySearch(arr, x, low=0, high=-1) {
    if (high === -1) {
      high = arr.length - 1;
    }
    if (low > high) {
      return false;
    } else {
      var mid = Math.floor((low + high) / 2);
      if (arr[mid] === x) {
        return true;
      } else if (arr[mid] > x) {
        return binarySearch(arr, x, low, mid-1);
      } else {
        return binarySearch(arr, x, mid+1, high);
      }
    }
}

4. Backtracking: Backtracking is a technique that can be used to find all possible solutions to a problem by building up a solution one step at a time and undoing previous steps if they lead to a dead end.

function generatePermutations(arr, index = 0) {
    if (index === arr.length) {
        console.log(arr);
    } else {
        for (let i = index; i < arr.length; i++) {
            [arr[index], arr[i]] = [arr[i], arr[index]];
            generatePermutations(arr, index + 1);
            [arr[index], arr[i]] = [arr[i], arr[index]];
        }
    }
}

5.Dynamic Programming: Dynamic Programming is a technique that can be used to solve problems recursively by breaking them down into smaller sub problems and storing the results of previous subproblems to avoid redundant work.

dfunction longestCommonSubsequence(str1, str2) {
    if (!str1 || !str2) {
        return "";
    } else if (str1[str1.length-1] === str2[str2.length-1]) {
        return longestCommonSubsequence(str1.slice(0, -1), str2.slice(0, -1)) + str1[str1.length-1];
    } else {
        var option1 = longestCommonSubsequence(str1, str2.slice(0, -1));
        var option2 = longestCommonSubsequence(str1.slice(0, -1), str2);
        return option1.length > option2.length ? option1 : option2;
    }
}

6. Recursive Data Structures: Recursive data structures are data structures that are defined recursively, such as linked lists and trees.

class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor(head = null) {
    this.head = head;
  }
}

In conclusion, recursion is a powerful programming concept that can be used to write elegant and efficient code. It is important to have a base case and a recursive case in a recursive function, and to use techniques like memoization, divide and conquer, backtracking and dynamic programming to optimize the function. Recursive data structures and generators are also powerful tools that can be used to solve problems in a elegant way.