Here’s what Google has to say on recursion – Did you mean: recursion
Strange, isn’t? Or not!!
Recursion is a problem-solving technique that involves breaking a problem into smaller instances of the same problem (also called subproblems) until we get a small enough subproblem having a trivial solution. We can say that recursion is “defining a problem in terms of itself” as it involves a function calling itself with a base case to terminate the infinite loop.
Recursion is an important concept in computer science and a very powerful tool in writing algorithms. It allows us to write very elegant solutions to problems that may otherwise be very difficult to implement iteratively. It might be a little confusing and difficult to understand, especially for beginners but once you understand it, a whole new world of programming will open for you. Recursion just takes practice to get good at and nothing is more interesting than finding a solution to a problem the recursive way.
Backtracking:
- Find all combinations of elements satisfying given constraintsMedium
- K–Partition Problem | Printing all partitionsHard
- Find all distinct combinations of a given length with repetition allowedMedium
- Print all combinations of numbers from 1 to
n
having sumn
Medium - Print all possible solutions to N–Queens problemHard
- Print all possible Knight’s tours on a chessboardHard
- Find the shortest path in a mazeMedium
- Find the longest possible route in a matrixMedium
- Find the path from source to destination in a matrix that satisfies given constraintsMedium
- Find the total number of unique paths in a maze from source to destinationMedium
- Magnet PuzzleHard
- Find all paths from the first cell to the last cell of a matrixMedium
- Print all shortest routes in a rectangular gridMedium
- Find all occurrences of the given string in a character matrixHard
- Generate a list of possible words from a character matrixHard
- Find all permutations of a string – C++, Java, PythonHard
- Print all distinct subsets of a given setHard
String:
- Check if a string is a rotated palindrome or notMedium
- Check if a repeated subsequence is present in a string or notHard
- Find all interleaving of given stringsEasy
- Find all possible combinations of words formed from the mobile keypadHard
- Find all possible combinations by replacing given digits with characters of the corresponding listHard
- Find all strings of a given length containing balanced parenthesesMedium
- Find all combinations of non-overlapping substrings of a stringMedium
- Determine whether a string is a palindrome or notEasy
- Print all combinations of phrases formed by picking words from each of the given listsMedium
- Break a string into all possible combinations of non-overlapping substringsMedium
- Remove adjacent duplicate characters from a stringEasy
- Find all n-digit strictly increasing numbers (Bottom-up and Top-down approach)Medium
- Find all n-digit binary numbers having more 1’s than 0’s for any prefixMedium
- Find all n-digit numbers with a given sum of digitsHard
- Find all n-digit binary numbers with an equal sum of bits in their two halvesHard
- Find all n-digit numbers with equal sum of digits at even and odd indicesHard
- Find all lexicographic permutations of a stringHard
- Reverse a string using recursionEasy
- Number to word conversionHard
- Implement strstr function in JavaEasy
- Find the minimum number possible by doing at-most
k
swapsMedium - Determine whether a string matches with a given patternHard
Array:
- Replace every array element with the product of every other elementMedium
- Find all distinct combinations of a given length – IMedium
- Find all distinct combinations of a given length – IIMedium
- Find a triplet with the given sum in an arrayMedium
- Reverse every consecutive
m
-elements of a subarrayMedium - Maximum Product Subset ProblemEasy
- 4–Sum Problem | Quadruplets with a given sumMedium
- Quickselect AlgorithmMedium
- Add elements of two arrays into a new arrayEasy
- Print all combinations of positive integers in increasing order that sums to a given numberHard
- 3–partition problem extended | Printing all partitionsHard
- Check if an array represents a min-heap or notMedium
- Convert max heap to min heap in linear timeEasy
- Find the odd occurring element in an array in logarithmic timeMedium
- Generate the power set of a given setMedium
Matrix:
- Print matrix in spiral orderMedium
- Replace all occurrences of 0 that are not surrounded by 1 in a binary matrixMedium
- Young Tableau | Insert, Search, Extract-Min, Delete, ReplaceHard
- Replace all occurrences of 0 that are surrounded by 1 in a binary matrixMedium
- Sort an array using Young tableauHard
- Flood Fill AlgorithmMedium
- Find the shortest path from source to destination in a matrix that satisfies given constraintsHard
- Find minimum passes required to convert all negative values in a matrixHard
Divide & Conquer:
- Binary Search AlgorithmEasy
- Find the number of rotations in a circularly sorted arrayEasy
- Find the smallest missing element from a sorted arrayMedium
- Find the number of 1’s in a sorted binary arrayEasy
- Find the peak element in an arrayMedium
- Maximum Subarray Sum using Divide and ConquerMedium
- Find floor and ceil of a number in a sorted array (Recursive solution)Easy
- Find the frequency of each element in a sorted array containing duplicatesEasy
- Find the minimum and maximum element in an array using Divide and ConquerEasy
- Longest Common Prefix (LCP) ProblemEasy
- Exponential searchEasy
- Unbounded Binary SearchEasy
- Efficiently implement power functionEasy
Linked List:
- Clone a Linked ListEasy
- Delete a linked listEasy
- Split a linked list into two lists where each list contains alternating elements from itMedium
- Construct a linked list by merging alternate nodes of two given listsEasy
- Merge two sorted linked lists into oneMedium
- Efficiently merge
k
sorted linked listsHard - Reverse a Linked List – Recursive SolutionHard
- Reverse every group of
k
nodes in a linked listMedium - Find k’th node from the end of a linked listEasy
- Merge alternate nodes of two linked lists into the first listMedium
- Delete every
N
nodes in a linked list after skippingM
nodesEasy - Rearrange linked list in a specific manner in linear timeMedium
- Check if a linked list is palindrome or notMedium
- Move the last node to the front of a linked listEasy
- Rearrange a linked list by separating odd nodes from even onesMedium
- Recursively check if the linked list of characters is palindrome or notMedium
- Add a single-digit number to a linked list representing a numberMedium
- Reverse every alternate group of
k
nodes in a linked listMedium - Determine whether a linked list is palindrome or notMedium
- Reverse a doubly linked listEasy
- Pairwise swap adjacent nodes of a linked listMedium
- Flatten a Linked ListHard
- Check if a linked list of strings is palindromicEasy
- Flatten a multilevel linked listMedium
- Clone a linked list with random pointerHard
- Update random pointer for each linked list node to point to the maximum nodeMedium
Sorting:
- Insertion Sort AlgorithmEasy
- Selection Sort AlgorithmEasy
- Bubble Sort AlgorithmEasy
- Merge Sort AlgorithmEasy
- Quicksort AlgorithmMedium
- Hybrid QuickSort AlgorithmMedium
- Quicksort using Dutch National Flag AlgorithmMedium
- Quicksort algorithm using Hoare’s partitioning schemeMedium
- Heap Sort AlgorithmMedium
- Introsort Algorithm – Overview and C++ ImplementationHard
- Merge sort algorithm for a singly linked listHard
- Sort a doubly-linked list using merge sortMedium
- Inversion count of an arrayHard
- Find surpasser count for each array elementHard
- Water Jugs ProblemHard
Binary Tree:
- Inorder Tree TraversalMedium
- Preorder Tree TraversalMedium
- Postorder Tree TraversalMedium
- Check if two binary trees are identical or notEasy
- Print bottom view of a binary treeMedium
- Print top view of a binary treeMedium
- In-place convert a binary tree to its sum treeEasy
- Determine whether the given binary tree nodes are cousins of each otherMedium
- Print cousins of a given node in a binary treeMedium
- Check if a binary tree is a sum tree or notMedium
- Combinations of words formed by replacing given numbers with corresponding alphabetsHard
- Determine whether a binary tree is a subtree of another binary treeMedium
- Find the diameter of a binary treeMedium
- Check if a binary tree is symmetric or notEasy
- Convert a binary tree to its mirrorEasy
- Determine if a binary tree can be converted to another by doing any number of swaps of childrenEasy
- Find the Lowest Common Ancestor (LCA) of two nodes in a binary treeMedium
- Print all paths from the root to leaf nodes of a binary treeEasy
- Find ancestors of a given node in a binary treeMedium
- Find distance between given pairs of nodes in a binary treeHard
- Find the diagonal sum of a binary treeMedium
- Sink nodes containing zero to the bottom of a binary treeHard
- Convert a binary tree to a full tree by removing half nodesMedium
- Truncate a binary tree to remove nodes that lie on a path having a sum less than
k
Medium - Find maximum sum root to leaf path in a binary treeMedium
- Check if a binary tree is height-balanced or notMedium
- Convert binary tree to Left-child right-sibling binary treeMedium
- Print all paths from leaf to root node of a binary treeMedium
- Find all nodes at a given distance from leaf nodes in a binary treeHard
- Count all subtrees having the same value of nodes in a binary treeMedium
- Find the maximum difference between a node and its descendants in a binary treeMedium
- Find the maximum sum path between two leaves in a binary treeHard
- Construct a binary tree from inorder and preorder traversalHard
- Construct a binary tree from inorder and postorder traversalsHard
- Construct a binary tree from inorder and level order sequenceHard
- Construct a full binary tree from the preorder sequence with leaf node informationHard
- Construct a full binary tree from a preorder and postorder sequenceHard
- Find postorder traversal of a binary tree from its inorder and preorder sequenceMedium
- Set next pointer to the inorder successor of all nodes in a binary treeEasy
- Find preorder traversal of a binary tree from its inorder and postorder sequenceHard
- Find difference between sum of all nodes present at odd and even levels in a binary treeEasy
- Clone a binary tree with random pointersHard
- Threaded Binary Tree – Overview and ImplementationMedium
- Determine if a binary tree satisfies the height-balanced property of a red–black treeMedium
- Construct an ancestor matrix from a binary treeEasy
- Find all possible binary trees having the same inorder traversalHard
- Perform boundary traversal on a binary treeMedium
- Check if each node of a binary tree has exactly one childEasy
- Evaluate a Binary Expression TreeEasy
- Construction of an expression treeEasy
- Fix children-sum property in a binary treeMedium
- Maximum path sum in a binary treeHard
- Create a mirror of an m–ary treeEasy
- Print a two-dimensional view of a binary treeEasy
- Construct a Cartesian tree from an inorder traversalMedium
- Calculate the height of a binary tree with leaf nodes forming a circular doubly linked listMedium
- Link nodes present in each level of a binary tree in the form of a linked listHard
- Convert a ternary tree to a doubly-linked listMedium
- Extract leaves of a binary tree into a doubly-linked listMedium
- Find the vertical sum of a binary treeHard
- In-place convert a binary tree to a doubly-linked listHard
- Check whether the leaf traversal of given binary trees is the same or notHard
- Efficiently print all nodes between two given levels in a binary treeEasy
- Calculate the height of a binary treeEasy
- Delete a binary treeEasy
- Level order traversal of a binary treeEasy
- Spiral order traversal of a binary treeMedium
- Reverse level order traversal of a binary treeEasy
- Print left view of a binary treeEasy
- Find the next node at the same level as the given node in a binary treeMedium
- Check if a binary tree is a complete binary tree or notMedium
- Print diagonal traversal of a binary treeMedium
- Invert Binary TreeEasy
- Convert a binary tree into a doubly-linked list in spiral orderHard
- Check if a binary tree is a min-heap or notMedium
- Invert alternate levels of a perfect binary treeHard
- Perform vertical traversal of a binary treeMedium
- Compute the maximum number of nodes at any level in a binary treeEasy
- Print right view of a binary treeMedium
- Find the minimum depth of a binary treeEasy
- Print nodes of a binary tree in vertical orderMedium
Binary Search Tree:
- Insertion in a BSTEasy
- Search a given key in BSTEasy
- Deletion from BST (Binary Search Tree)Medium
- Construct a balanced BST from the given keysEasy
- Determine whether a given binary tree is a BST or notMedium
- Check if the given keys represent the same BSTs or not without building BSTHard
- Find inorder predecessor for the given key in a BSTMedium
- Find the Lowest Common Ancestor (LCA) of two nodes in a BSTEasy
- Find k’th smallest and k’th largest element in a BSTEasy
- Find floor and ceil in a Binary Search TreeMedium
- Convert a binary tree to BST by maintaining its original structureMedium
- Remove nodes from a BST that have keys outside a valid rangeMedium
- Find a pair with the given sum in a BSTEasy
- Find k’th smallest node in a Binary Search Tree (BST)Easy
- Find inorder successor for the given key in a BSTMedium
- Fix a binary tree that is only one swap away from becoming a BSTHard
- Update every key in a BST to contain the sum of all greater keysMedium
- Check if a given sequence represents the preorder traversal of a BSTHard
- Build a Binary Search Tree from a postorder sequenceHard
- Build a Binary Search Tree from a preorder sequenceHard
- Count subtrees in a BST whose nodes lie within a given rangeMedium
- Find the size of the largest BST in a binary treeHard
- Print complete Binary Search Tree (BST) in increasing orderEasy
- Print binary tree structure with its contents in C++Medium
- Treap Data StructureBeginner
- Implementation of Treap Data Structure (Insert, Search, and Delete)Hard
- Merge two BSTs into a doubly-linked list in sorted orderHard
- Construct a height-balanced BST from an unbalanced BSTHard
- Construct a height-balanced BST from a sorted doubly linked listHard
- Find a triplet with the given sum in a BSTHard
- Convert a Binary Search Tree into a Min HeapHard
Dynamic Programming:
- Longest Common Subsequence ProblemMedium
- Longest Common Subsequence of k–sequencesMedium
- Longest Common Subsequence | Finding all LCSHard
- Longest Palindromic Subsequence using Dynamic ProgrammingMedium
- Longest Repeated Subsequence ProblemMedium
- Implement Diff UtilityMedium
- Shortest Common Supersequence ProblemMedium
- Shortest Common Supersequence | Finding all SCSHard
- Shortest Common Supersequence Problem using LCSHard
- Longest Increasing Subsequence using Dynamic ProgrammingHard
- Longest Decreasing Subsequence ProblemHard
- Maximum Sum Increasing Subsequence ProblemMedium
- The Levenshtein distance (Edit distance) ProblemMedium
- Find the size of the largest square submatrix of 1’s present in a binary matrixMedium
- Matrix Chain Multiplication using Dynamic ProgrammingHard
- Find minimum cost to reach the last cell of a matrix from its first cellMedium
- Find the longest sequence formed by adjacent numbers in the matrixMedium
- Count the number of paths in a matrix with a given cost to reach the destination cellMedium
- 0–1 Knapsack ProblemMedium
- Partition Problem using Dynamic ProgrammingMedium
- Subset Sum Problem – Dynamic Programming SolutionMedium
- 3–Partition ProblemMedium
- Minimum Sum Partition ProblemHard
- Rod Cutting ProblemMedium
- Maximum Product Rod CuttingMedium
- Coin change-making problemMedium
- Coin Change ProblemHard
- Total possible solutions to a linear equation of
k
variablesHard - Longest Alternating Subsequence ProblemMedium
- Count the number of times a pattern appears in a given string as a subsequenceHard
- Collect maximum points in a matrix by satisfying given constraintsHard
- Find all N-digit binary strings without any consecutive 1’sEasy
- Count total possible combinations of n-digit numbers in a mobile keypadMedium
- Word Break Problem – Dynamic ProgrammingHard
- Check if a string is k–palindrome or notHard
- Find total ways to achieve a given sum with
n
throws of dice havingk
facesMedium - Wildcard Pattern MatchingHard
- Find the number of ways to fill an
N × 4
matrix with1 × 4
tilesMedium - Ways to reach the bottom-right corner of a matrix with exactly
k
turns allowedHard - Weighted Interval Scheduling ProblemMedium
- Find total ways to reach n’th stair with at-most
m
stepsMedium - Find total ways to reach the n’th stair from the bottomMedium
- Find the minimum number of deletions required to convert a string into a palindromeMedium
- Pots of Gold Game Problem using Dynamic ProgrammingHard
- Find minimum cuts needed for the palindromic partition of a stringHard
- Find minimum jumps required to reach the destinationMedium
- Find the probability that a person is alive after taking
n
steps on an islandMedium - Longest Increasing Subsequence using LCSMedium
- Count all paths in a matrix from the first cell to the last cellEasy
- Check if a string matches with the given wildcard patternHard
- Check if a string is interleaving of two other given stringsMedium
- Find all employees who directly or indirectly reports to a managerHard
- Find optimal cost to construct a binary search treeHard
- Find the maximum sum of a subsequence with no adjacent elementsMedium
- Minimum-weight triangulation of a convex polygonHard
- Find maximum profit that can be earned by conditionally selling stocksEasy
- Program to find n’th Fibonacci numberEasy
- Count decodings of a given sequence of digitsMedium
- Hat Check Problem – Counting DerangementsMedium
- Maximum Independent Set ProblemMedium
- Find the minimum number of squares that sum to a given numberMedium
- Truncate an integer array such that
2×min
becomes more thanmax
Hard - Find ways to calculate a target from elements of the specified arrayMedium
- Find the length of the longest path in a matrix with consecutive charactersMedium
- Collect maximum value of coins in a matrixHard
- Single-Source Shortest Paths – Bellman–Ford AlgorithmMedium
- All-Pairs Shortest Paths – Floyd Warshall AlgorithmEasy
Programming Puzzles:
- Implement power function without using multiplication and division operatorsEasy
- Print all numbers between 1 to N without using a semicolonMedium
- Determine the if condition to print the specific outputEasy
- Tower of Hanoi ProblemMedium
- Print all numbers between 1 to N without using any loop | 4 methodsEasy
- Multiply two numbers without using a multiplication operator or loopsEasy
- Find minimum number without using conditional statement or ternary operatorMedium
- Perform division of two numbers without using division operatorMedium
- Find maximum number without using conditional statement or ternary operatorEasy
Graphs:
- Depth First Search (DFS)Medium
- Breadth-First Search (BFS)Medium
- Arrival and departure time of vertices in DFSEasy
- Determine whether a graph is Bipartite using DFSMedium
- Topological Sort Algorithm for DAGMedium
- Transitive closure of a graphEasy
- Determine whether an undirected graph is a tree (Acyclic Connected Graph)Medium
- 2–Edge Connectivity in a graphHard
- Check if a digraph is a DAG (Directed Acyclic Graph) or notMedium
- Disjoint–Set Data Structure (Union–Find Algorithm)Medium
- Check if a graph is strongly connected or notEasy
- Check if a graph is strongly connected or not using one DFS TraversalHard
- Union–Find Algorithm for cycle detection in a graphMedium
- Find the cost of the shortest path in DAG using one pass of Bellman–FordMedium
- Find all Possible Topological Orderings of a DAGHard
- Find correct order of alphabets in a given dictionary of ancient originHard
- Find the longest path in a Directed Acyclic Graph (DAG)Hard
- Print all k–colorable configurations of a graph (Vertex coloring of a graph)Medium
- Print all Hamiltonian paths present in a graphHard
- Kruskal’s Algorithm for finding Minimum Spanning TreeHard
- Eulerian cycle in directed graphsHard
- Find root vertex of a graphMedium
- Check whether an undirected graph is EulerianMedium
- Check if a set of words can be rearranged to form a circleHard
- Find itinerary from the given list of departure and arrival airportsEasy
- Check if an undirected graph contains a cycle or notMedium
- Compute the least cost path in a weighted digraph using BFSMedium
- Find the path between given vertices in a directed graphEasy
Stack:
- Recursive solution to sort a stackHard
- Reverse a stack using recursionHard
- Reverse a string using a stack data structureEasy
- Reverse an array in C++Easy
- Find all binary strings that can be formed from a wildcard patternMedium
- Implement a stack using the queue data structureMedium
- Implement a queue using the stack data structureMedium
Trie:
- Lexicographic sorting of a given set of keysMedium
- Find the maximum occurring word in a given set of stringsEasy
- Find first
k
maximum occurring words in a given set of stringsMedium - Word Break Problem – Using Trie Data StructureMedium
- Find all words matching a pattern in the given dictionaryMedium
- Find the shortest unique prefix for every word in an arrayMedium