Recursion is a programming concept that involves a function calling itself directly or indirectly to solve a problem
- Tree Structures:
- Recursion is commonly used for operations on tree structures. For example, in a binary tree, a recursive function can be used to traverse the tree, perform operations on each node, or search for a specific node.
- Graphs:
- Similarly, in graph data structures, recursion can be employed for graph traversal and various graph algorithms. Depth-First Search (DFS) is a classic example where recursion is often used to explore deeper into the graph.
- Linked Lists:
- Recursion can be applied to linked lists for operations such as reversing a linked list or merging two sorted linked lists. Each recursive call can handle a smaller portion of the list.
Recursion in Algorithms:
- Sorting:
- Recursive algorithms are commonly used in sorting. For instance, the quicksort algorithm is a well-known sorting algorithm that uses recursion to divide the array into smaller subarrays.
- Searching:
- Recursive algorithms are also found in searching algorithms. Binary search is an example where recursion is used to search in a sorted array by dividing it into halves.
- Divide and Conquer:
- Many divide-and-conquer algorithms use recursion. This approach involves breaking a problem into smaller subproblems, solving them recursively, and then combining the solutions to solve the original problem. Merge sort is an example of a divide-and-conquer algorithm.
DSA Poblem statement in Recurson:
Factorial and Combinatorial Problems:
- Factorial Calculation:
- Write a recursive function to calculate the factorial of a given number.
- Binomial Coefficient:
- Implement a recursive function to calculate the binomial coefficient C(n, k).
- Permutations:
- Write a recursive function to generate all permutations of a given set of elements.
- Combinations:
- Implement a recursive function to generate all combinations of a given set of elements.
Fibonacci Sequence Problems:
- Nth Fibonacci Number:
- Write a recursive function to calculate the nth Fibonacci number.
- Fibonacci Series:
- Generate the Fibonacci series up to the nth term using recursion.
- Memoization in Fibonacci:
- Optimize the recursive Fibonacci function using memoization.
Tree Traversal Problems:
- Preorder Traversal:
- Implement a recursive function for preorder traversal of a binary tree.
- Inorder Traversal:
- Write a recursive function for inorder traversal of a binary tree.
- Postorder Traversal:
- Implement a recursive function for postorder traversal of a binary tree.
Search and Sort Problems:
- Binary Search:
- Write a recursive function to perform binary search on a sorted array.
- Merge Sort:
- Implement the merge sort algorithm using recursion.
- Quick Sort:
- Write a recursive function to implement the quicksort algorithm.
Dynamic Programming Problems:
- Coin Change Problem:
- Solve the coin change problem using recursion.
- Rod Cutting Problem:
- Implement a recursive solution for the rod cutting problem.
- Longest Common Subsequence:
- Write a recursive function to find the length of the longest common subsequence.
Backtracking Problems:
- N-Queens Problem:
- Solve the N-Queens problem using recursion and backtracking.
- Sudoku Solver:
- Implement a recursive function to solve a Sudoku puzzle.
- Subset Sum:
- Write a recursive function to find subsets that sum to a given target.
Graph Traversal Problems:
- Depth-First Search (DFS):
- Implement DFS for a graph using recursion.
- Breadth-First Search (BFS):
- Write a recursive function for BFS traversal of a graph.
- Connected Components:
- Find the connected components in an undirected graph using recursion.
Divide and Conquer Problems:
- Binary Exponentiation:
- Implement binary exponentiation using recursion.
- Merge Overlapping Intervals:
- Write a recursive function to merge overlapping intervals.
- Closest Pair of Points:
- Solve the closest pair of points problem using recursion.
String Manipulation Problems:
- Reverse a String:
- Write a recursive function to reverse a string.
- Palindrome Check:
- Implement a recursive function to check if a string is a palindrome.
- Generate Parentheses:
- Generate all valid combinations of n pairs of parentheses.
Miscellaneous Recursion Problems:
- Tower of Hanoi:
- Solve the Tower of Hanoi problem using recursion.
- Subset Generation:
- Generate all possible subsets of a given set.
- Josephus Problem:
- Find the survivor in the Josephus problem using recursion.
- Power Set:
- Implement a recursive function to generate the power set of a set.
- Counting Paths in a Grid:
- Count all possible paths from the top-left to the bottom-right of a grid.
- Pascal’s Triangle:
- Generate Pascal’s triangle up to a given number of rows using recursion.
- Maximal Square:
- Find the size of the largest square of ‘1’s in a binary matrix.
- Unique Paths:
- Count the number of unique paths from the top-left to the bottom-right of a grid.
- Gray Code:
- Generate the n-bit gray code sequence using recursion.
- Palindrome Partitioning:
- Partition a string into palindrome substrings.
- Letter Combinations of a Phone Number:
- Generate all possible letter combinations of a phone number.
- Decode Ways:
- Count the number of ways to decode a given message.
- Word Search:
- Check if a word exists in a 2D board.
- Expression Add Operators:
- Given a string that represents a number, implement a function to add operators (+, -, *) between digits to get a target value.
- Longest Increasing Subsequence:
- Find the length of the longest increasing subsequence in an array.
- Maximum Subarray Sum:
- Find the contiguous subarray with the largest sum.
- Jump Game:
- Determine if you can reach the last index of an array.
- Combination Sum:
- Find all unique combinations in candidates where the candidate numbers sum to a given target.
- Number of Islands:
- Given a 2D grid, count the number of islands.
- Binary Tree Maximum Path Sum:
- Find the maximum path sum between two nodes in a binary tree.
- Expression Evaluation:
- Evaluate an arithmetic expression with parentheses using recursion.
- Minimum Window Substring:
- Find the minimum window in a string that contains all characters of another string.
1. Factorial Calculation:
function factorial(n) {
if (n === 0 || n === 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}2. Fibonacci Series:
function fibonacci(n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}3. Sum of Digits:
function sum_of_digits(n) {
if (n < 10) {
return n;
} else {
return n % 10 + sum_of_digits(Math.floor(n / 10));
}
}
4. Power Function:
function power(base, exponent) {
if (exponent === 0) {
return 1;
} else {
return base * power(base, exponent – 1);
}
}
5. Binary Search:
function binary_search(arr, low, high, target) {
if (low <= high) {
let mid = Math.floor((low + high) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
return binary_search(arr, mid + 1, high, target);
} else {
return binary_search(arr, low, mid – 1, target);
}
} else {
return -1;
}
}
6. Tower of Hanoi:
function tower_of_hanoi(n, source, auxiliary, target) {
if (n === 1) {
console.log(`Move disk 1 from ${source} to ${target}`);
} else {
tower_of_hanoi(n – 1, source, target, auxiliary);
console.log(`Move disk ${n} from ${source} to ${target}`);
tower_of_hanoi(n – 1, auxiliary, source, target);
}
}
7. Palindrome Check:
function isPalindrome(str) {
str = str.toLowerCase().replace(/[^a-z]/g, ”); // Convert to lowercase and remove non-alphabetic characters
if (str.length <= 1) {
return true;
} else if (str[0] === str[str.length – 1]) {
return isPalindrome(str.slice(1, -1));
} else {
return false;
}
}
8. Greatest Common Divisor (GCD):
function gcd(a, b) {
if (b === 0) {
return a;
} else {
return gcd(b, a % b);
}
}
// Example usage:
console.log(gcd(48, 18)); // 6
9. Sum of Array Elements:
function sumArray(arr) {
if (arr.length === 0) {
return 0;
} else {
return arr[0] + sumArray(arr.slice(1));
}
}
// Example usage:
console.log(sumArray([1, 2, 3, 4, 5])); // 15
10. Binary Exponentiation:
function powerBinary(base, exponent) {
if (exponent === 0) {
return 1;
} else if (exponent % 2 === 0) {
let halfPower = powerBinary(base, exponent / 2);
return halfPower * halfPower;
} else {
return base * powerBinary(base, exponent – 1);
}
}
// Example usage:
console.log(powerBinary(2, 5)); // 32
11. Reverse a String:
function reverseString(str) {
if (str === “”) {
return str;
} else {
return reverseString(str.substr(1)) + str[0];
}
}
// Example usage:
console.log(reverseString(“hello”)); // “olleh”
12. Counting Down:
function countdown(n) {
if (n <= 0) {
console.log(“Done!”);
} else {
console.log(n);
countdown(n – 1);
}
}
// Example usage:
countdown(5);
// Outputs:
// 5
// 4
// 3
// 2
// 1
// Done!
13. Flatten Nested Arrays:
function flattenArray(arr) {
let result = [];
arr.forEach(function (element) {
if (Array.isArray(element)) {
result = result.concat(flattenArray(element));
} else {
result.push(element);
}
});
return result;
}
// Example usage:
console.log(flattenArray([1, [2, [3, 4], 5], 6])); // [1, 2, 3, 4, 5, 6]
14. Calculate Factorial using Ternary Operator:
function factorialTernary(n) {
return n === 0 ? 1 : n * factorialTernary(n – 1);
}
// Example usage:
console.log(factorialTernary(5)); // 120
15. Print Fibonacci Series:
function fibonacciPrint(n, a = 0, b = 1) {
if (n > 0) {
console.log(a);
fibonacciPrint(n – 1, b, a + b);
}
}
// Example usage:
fibonacciPrint(5);
// Outputs:
// 0
// 1
// 1
// 2
// 3
16. Check if a Number is Even or Odd:
function isEven(n) {
if (n === 0) {
return true;
} else if (n === 1) {
return false;
} else {
return isEven(Math.abs(n) – 2);
}
}
// Example usage:
console.log(isEven(4)); // true
console.log(isEven(7)); // false
17. Calculate the Sum of Natural Numbers:
function sumOfNaturalNumbers(n) {
if (n === 1) {
return 1;
} else {
return n + sumOfNaturalNumbers(n – 1);
}
}
// Example usage:
console.log(sumOfNaturalNumbers(5)); // 15
18. Capitalize Each Word in a String:
function capitalizeWords(str) {
let words = str.split(‘ ‘);
if (words.length === 0) {
return ”;
} else {
return words[0].charAt(0).toUpperCase() + words[0].slice(1) + ‘ ‘ + capitalizeWords(words.slice(1).join(‘ ‘));
}
}
// Example usage:
console.log(capitalizeWords(“hello world”)); // “Hello World”
19. Check for Prime Number:
function isPrime(n, i = 2) {
if (n <= 2) {
return (n === 2);
}
if (n % i === 0) {
return false;
}
if (i * i > n) {
return true;
}
return isPrime(n, i + 1);
}
// Example usage:
console.log(isPrime(11)); // true
console.log(isPrime(6)); // false
20. Calculate the Length of a String:
function stringLength(str) {
if (str === ”) {
return 0;
} else {
return 1 + stringLength(str.slice(1));
}
}
// Example usage:
console.log(stringLength(“recursive”)); // 9
21. Check for a Subset:
function isSubset(arr1, arr2, m, n) {
if (m === 0) {
return true;
}
if (n === 0) {
return false;
}
if (arr1[m – 1] === arr2[n – 1]) {
return isSubset(arr1, arr2, m – 1, n – 1);
}
return isSubset(arr1, arr2, m, n – 1);
}
// Example usage:
const arr1 = [3, 4, 5];
const arr2 = [1, 2, 3, 4, 5];
console.log(isSubset(arr1, arr2, arr1.length, arr2.length)); // true
22. Calculate the Greatest Common Divisor (GCD) using Euclidean Algorithm:
function gcdEuclidean(a, b) {
return b === 0 ? a : gcdEuclidean(b, a % b);
}
// Example usage:
console.log(gcdEuclidean(48, 18)); // 6
23. Check for a Palindromic String:
function isPalindromeString(str) {
str = str.toLowerCase().replace(/[^a-z]/g, ”); // Convert to lowercase and remove non-alphabetic characters
if (str.length <= 1) {
return true;
} else if (str[0] === str[str.length – 1]) {
return isPalindromeString(str.slice(1, -1));
} else {
return false;
}
}
// Example usage:
console.log(isPalindromeString(“A man, a plan, a canal: Panama”)); // true
24. Generate Power Set:
function powerSet(input, index = 0, currentSubset = []) {
const n = input.length;
if (index === n) {
console.log(currentSubset);
return;
}
powerSet(input, index + 1, currentSubset);
currentSubset.push(input[index]);
powerSet(input, index + 1, currentSubset);
currentSubset.pop();
}
// Example usage:
powerSet([1, 2, 3]);
// Outputs:
// []
// [3]
// [2]
// [2, 3]
// [1]
// [1, 3]
// [1, 2]
// [1, 2, 3]
25. Calculate Fibonacci Series using Memoization:
function fibonacciMemoization(n, memo = {}) {
if (n <= 1) {
return n;
}
if (!memo[n]) {
memo[n] = fibonacciMemoization(n – 1, memo) + fibonacciMemoization(n – 2, memo);
}
return memo[n];
}
// Example usage:
console.log(fibonacciMemoization(5)); // 5
26. Calculate Combination (n choose k):
function combination(n, k) {
if (k === 0 || k === n) {
return 1;
} else {
return combination(n – 1, k – 1) + combination(n – 1, k);
}
}
// Example usage:
console.log(combination(5, 2)); // 10
27. Print Numbers in a Range:
function printRange(start, end) {
if (start > end) {
return;
}
console.log(start);
printRange(start + 1, end);
}
// Example usage:
printRange(3, 8);
// Outputs:
// 3
// 4
// 5
// 6
// 7
// 8
28. Check if a Word is a Palindrome:
function isPalindromeWord(word) {
word = word.toLowerCase().replace(/[^a-z]/g, ”); // Convert to lowercase and remove non-alphabetic characters
if (word.length <= 1) {
return true;
} else if (word[0] === word[word.length – 1]) {
return isPalindromeWord(word.slice(1, -1));
} else {
return false;
}
}
// Example usage:
console.log(isPalindromeWord(“level”)); // true
29. Calculate Exponentiation using Iteration:
function powerIteration(base, exponent) {
let result = 1;
for (let i = 0; i < exponent; i++) {
result *= base;
}
return result;
}
// Example usage:
console.log(powerIteration(2, 3)); // 8
30. Generate Permutations:
function permutations(str, prefix = ”) {
const n = str.length;
if (n === 0) {
console.log(prefix);
} else {
for (let i = 0; i < n; i++) {
const rem = str.slice(0, i) + str.slice(i + 1);
permutations(rem, prefix + str[i]);
}
}
}
// Example usage:
permutations(‘abc’);
// Outputs:
// abc
// acb
// bac
// bca
// cab
// cba
31. Tower of Hanoi:
The Tower of Hanoi is a classic problem that involves moving a tower of disks from one rod to another, with the constraint that only one disk can be moved at a time, and no disk can be placed on top of a smaller disk.
function towerOfHanoi(n, sourceRod, auxiliaryRod, targetRod) {
if (n === 1) {
console.log(`Move disk 1 from ${sourceRod} to ${targetRod}`);
} else {
// Move n-1 disks from source to auxiliary rod using target rod
towerOfHanoi(n – 1, sourceRod, targetRod, auxiliaryRod);
// Move the nth disk from source to target rod
console.log(`Move disk ${n} from ${sourceRod} to ${targetRod}`);
// Move the n-1 disks from auxiliary rod to target rod using source rod
towerOfHanoi(n – 1, auxiliaryRod, sourceRod, targetRod);
}
}
// Example usage:
towerOfHanoi(3, ‘A’, ‘B’, ‘C’);
Explanation:
- The function towerOfHanoi takes four parameters: n (number of disks), sourceRod (the rod from which disks are moved), auxiliaryRod (the auxiliary rod used for moving disks), and targetRod (the rod to which disks are moved).
- The base case if (n === 1) handles the situation when there’s only one disk to move. In this case, it prints the move statement.
- In the recursive case, it breaks down the problem into three steps:
- Move the top n-1 disks from the source rod to the auxiliary rod, using the target rod as the intermediary.
- Move the nth disk from the source rod to the target rod.
- Move the n-1 disks from the auxiliary rod to the target rod, using the source rod as the intermediary.
32. Depth-First Search (DFS) on a Graph:
Depth-First Search is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It is often used to explore and analyze graphs.
class Graph {
constructor() {
this.vertices = [];
this.adjacencyList = new Map();
}
addVertex(vertex) {
this.vertices.push(vertex);
this.adjacencyList.set(vertex, []);
}
addEdge(source, destination) {
this.adjacencyList.get(source).push(destination);
this.adjacencyList.get(destination).push(source); // for an undirected graph
}
dfs(startVertex, visited = new Set()) {
console.log(startVertex);
visited.add(startVertex);
const neighbors = this.adjacencyList.get(startVertex);
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
this.dfs(neighbor, visited);
}
}
}
}
// Example usage:
const graph = new Graph();
graph.addVertex(‘A’);
graph.addVertex(‘B’);
graph.addVertex(‘C’);
graph.addVertex(‘D’);
graph.addEdge(‘A’, ‘B’);
graph.addEdge(‘B’, ‘C’);
graph.addEdge(‘C’, ‘D’);
graph.addEdge(‘D’, ‘A’);
graph.dfs(‘A’);
Explanation:
- The Graph class is implemented with methods for adding vertices and edges, and a dfs method for performing Depth-First Search.
- The dfs method takes a starting vertex and a set of visited vertices as parameters. It logs the current vertex, marks it as visited, and then recursively calls dfs on its unvisited neighbors.
- The example usage creates a simple undirected graph and performs a Depth-First Search starting from vertex ‘A’. The sequence of visited vertices will be printed.
Depth-First Search is a fundamental algorithm used in various applications, including topological sorting, pathfinding, and cycle detection in graphs
Recursion Problems Solving, Google, Amazon and Microsfot interview Question with answer with full explaination
Problem Statement:
Write a function to calculate the nth Fibonacci number using recursion.
function fibonacci(n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n – 1) + fibonacci(n – 2);
}
}
// Example usage:
console.log(fibonacci(5)); // Output: 5
Explanation:
- The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones. It starts with 0 and 1. So, the sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so forth.
- In the solution, the base case is when n is less than or equal to 1, in which case the function returns n.
- The recursive case calculates the Fibonacci number for n by adding the results of the Fibonacci function for n – 1 and n – 2.
Why Use Recursion for this Problem:
- Natural Representation:
- The Fibonacci sequence is naturally defined recursively. The nth Fibonacci number is the sum of the (n-1)th and (n-2)th Fibonacci numbers.
- Code Readability:
- The recursive solution closely reflects the mathematical definition of the Fibonacci sequence, making the code more readable and easy to understand.
- Simplicity:
- Recursive solutions are often simpler and more concise for problems that can be naturally divided into smaller subproblems.
Where This Problem is Used:
- Mathematics:
- The Fibonacci sequence and its properties have applications in various mathematical concepts, such as number theory and geometry.
- Dynamic Programming:
- While recursion is a simple way to understand and define the Fibonacci sequence, dynamic programming is often used to optimize the computation of Fibonacci numbers by avoiding redundant calculations.
- Algorithms and Data Structures:
- Understanding recursion and the Fibonacci sequence serves as a foundational concept when learning about algorithms and data structures. It’s a common problem used to illustrate recursion in introductory programming courses.
Important Note:
- While recursion is a powerful and elegant approach, it may not be the most efficient for calculating large Fibonacci numbers due to redundant calculations.
- Dynamic programming techniques, such as memoization or bottom-up approaches, are often preferred for optimization in real-world scenarios.
Problem Statement:
Write a function that calculates the total size of a directory and its subdirectories on a computer’s file system.
const fs = require(‘fs’);
const path = require(‘path’);
function calculateDirectorySize(dirPath) {
let totalSize = 0;
const files = fs.readdirSync(dirPath);
files.forEach(file => {
const filePath = path.join(dirPath, file);
const stats = fs.statSync(filePath);
if (stats.isDirectory()) {
totalSize += calculateDirectorySize(filePath); // Recursive call for subdirectories
} else {
totalSize += stats.size;
}
});
return totalSize;
}
// Example usage:
const directoryPath = ‘/path/to/your/directory’;
const sizeInBytes = calculateDirectorySize(directoryPath);
console.log(`Total Size of ${directoryPath}: ${sizeInBytes} bytes`);
Explanation:
- The function calculateDirectorySize takes a directory path as input and uses the Node.js fs (File System) module to read the contents of the directory.
- For each file or subdirectory in the directory, it checks whether it is a directory or a file using fs.statSync. If it’s a directory, the function makes a recursive call to calculateDirectorySize for that subdirectory.
- The size of each file is added to the totalSize variable.
- The function returns the total size of the directory and its subdirectories.
Why Use Recursion for this Problem:
- Nested Structure:
- Directories can contain subdirectories, which can further contain more subdirectories. Recursion is a natural fit for problems with nested structures.
- Modularity:
- Recursive solutions can be more modular and easier to understand, as the function works on a single directory and delegates the size calculation of subdirectories to recursive calls.
- Dynamic Problem Size:
- The size of a directory can vary, and recursion allows the algorithm to adapt to the dynamic structure of the file system.
Where This Problem is Used:
- Disk Space Management:
- Calculating the size of directories is crucial for managing disk space on a computer. This information is often used to identify large files or directories that may need attention.
- File Explorer Applications:
- File explorer applications use similar algorithms to display the size of directories when users browse their file systems.
- Backup Systems:
- Backup systems may use directory size calculations to estimate storage requirements for creating backups.
- Disk Cleanup Tools:
- Tools that help users clean up unnecessary files or directories on their systems may use directory size calculations to identify space-consuming items.
Important Note:
- While recursion is a suitable approach for understanding and solving this problem, large and deeply nested directory structures might lead to a stack overflow error.
Problem:
Determine whether a given string is a palindrome, which reads the same backward as forward.
function isPalindrome(str) {
const n = str.length;
if (n === 0 || n === 1) {
return true;
} else if (str[0] !== str[n – 1]) {
return false;
} else {
return isPalindrome(str.substring(1, n – 1));
}
}
Explanation:
A palindrome is a string that reads the same backward as forward, such as “madam” or “racecar”. The recursive solution to this problem works by checking if the first and last characters of the string are the same. If they are, it recursively checks the remaining substring. If they are not, it immediately returns false.
Application:
Palindromes are used in various literary and computational applications, including wordplay, pattern recognition, and error detection.
N-Queens Problem:
Problem: Place N queens on an N x N chessboard such that no two queens can attack each other (no two queens can share the same row, column, or diagonal).
function solveNQueens(n) {
const board = new Array(n);
for (let i = 0; i < n; i++) {
board[i] = new Array(n).fill(0);
}
if (placeNQueens(board, 0)) {
return board;
} else {
return [];
}
}
function placeNQueens(board, row) {
if (row >= board.length) {
return true;
}
for (let col = 0; col < board.length; col++) {
if (isSafe(board, row, col)) {
board[row][col] = 1;
if (placeNQueens(board, row + 1)) {
return true;
}
board[row][col] = 0;
}
}
return false;
}
function isSafe(board, row, col) {
for (let i = 0; i < row; i++) {
if (board[i][col] === 1) {
return false;
}
}
for (let i = row, j = col; i >= 0 && j >= 0; i–, j–) {
if (board[i][j] === 1) {
return false;
}
}
for (let i = row, j = col + row; i >= 0 && j < board.length; i–, j++) {
if (board[i][j] === 1) {
return false;
}
}
return true;
}
Explanation:
The N-queens problem is a classic problem in computer science that asks for the placement of N queens on an N x N chessboard such that no two queens can attack each other. The recursive solution to this problem works by backtracking, which means it tries different placements of queens and backtracks if it finds a placement that leads to a conflict.
Application:
The N-queens problem is used in various computational applications, including constraint satisfaction problems, search algorithms, and artificial intelligence.
E-Commerce application in Nodejs Backend Development Project