Recursion Practice Problems with Solutions

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:

1. Find all combinations of elements satisfying given constraintsMedium
2. K–Partition Problem | Printing all partitionsHard
3. Find all distinct combinations of a given length with repetition allowedMedium
4. Print all combinations of numbers from 1 to n having sum nMedium
5. Print all possible solutions to N–Queens problemHard
6. Print all possible Knight’s tours on a chessboardHard
7. Find the shortest path in a mazeMedium
8. Find the longest possible route in a matrixMedium
9. Find the path from source to destination in a matrix that satisfies given constraintsMedium
10. Find the total number of unique paths in a maze from source to destinationMedium
11. Magnet PuzzleHard
12. Find all paths from the first cell to the last cell of a matrixMedium
13. Print all shortest routes in a rectangular gridMedium
14. Find all occurrences of the given string in a character matrixHard
15. Generate a list of possible words from a character matrixHard
16. Find all permutations of a string – C++, Java, PythonHard
17. Print all distinct subsets of a given setHard

String:

1. Check if a string is a rotated palindrome or notMedium
2. Check if a repeated subsequence is present in a string or notHard
3. Find all interleaving of given stringsEasy
4. Find all possible combinations of words formed from the mobile keypadHard
5. Find all possible combinations by replacing given digits with characters of the corresponding listHard
6. Find all strings of a given length containing balanced parenthesesMedium
7. Find all combinations of non-overlapping substrings of a stringMedium
8. Determine whether a string is a palindrome or notEasy
9. Print all combinations of phrases formed by picking words from each of the given listsMedium
10. Break a string into all possible combinations of non-overlapping substringsMedium
11. Remove adjacent duplicate characters from a stringEasy
12. Find all n-digit strictly increasing numbers (Bottom-up and Top-down approach)Medium
13. Find all n-digit binary numbers having more 1’s than 0’s for any prefixMedium
14. Find all n-digit numbers with a given sum of digitsHard
15. Find all n-digit binary numbers with an equal sum of bits in their two halvesHard
16. Find all n-digit numbers with equal sum of digits at even and odd indicesHard
17. Find all lexicographic permutations of a stringHard
18. Reverse a string using recursionEasy
19. Number to word conversionHard
20. Implement strstr function in JavaEasy
21. Find the minimum number possible by doing at-most k swapsMedium
22. Determine whether a string matches with a given patternHard

Array:

1. Replace every array element with the product of every other elementMedium
2. Find all distinct combinations of a given length – IMedium
3. Find all distinct combinations of a given length – IIMedium
4. Find a triplet with the given sum in an arrayMedium
5. Reverse every consecutive m-elements of a subarrayMedium
6. Maximum Product Subset ProblemEasy
7. 4–Sum Problem | Quadruplets with a given sumMedium
8. Quickselect AlgorithmMedium
9. Add elements of two arrays into a new arrayEasy
10. Print all combinations of positive integers in increasing order that sums to a given numberHard
11. 3–partition problem extended | Printing all partitionsHard
12. Check if an array represents a min-heap or notMedium
13. Convert max heap to min heap in linear timeEasy
14. Find the odd occurring element in an array in logarithmic timeMedium
15. Generate the power set of a given setMedium

Matrix:

1. Print matrix in spiral orderMedium
2. Replace all occurrences of 0 that are not surrounded by 1 in a binary matrixMedium
3. Young Tableau | Insert, Search, Extract-Min, Delete, ReplaceHard
4. Replace all occurrences of 0 that are surrounded by 1 in a binary matrixMedium
5. Sort an array using Young tableauHard
6. Flood Fill AlgorithmMedium
7. Find the shortest path from source to destination in a matrix that satisfies given constraintsHard
8. Find minimum passes required to convert all negative values in a matrixHard

Divide & Conquer:

1. Binary Search AlgorithmEasy
2. Find the number of rotations in a circularly sorted arrayEasy
3. Find the smallest missing element from a sorted arrayMedium
4. Find the number of 1’s in a sorted binary arrayEasy
5. Find the peak element in an arrayMedium
6. Maximum Subarray Sum using Divide and ConquerMedium
7. Find floor and ceil of a number in a sorted array (Recursive solution)Easy
8. Find the frequency of each element in a sorted array containing duplicatesEasy
9. Find the minimum and maximum element in an array using Divide and ConquerEasy
10. Longest Common Prefix (LCP) ProblemEasy
11. Exponential searchEasy
12. Unbounded Binary SearchEasy
13. Efficiently implement power functionEasy

Linked List:

1. Clone a Linked ListEasy
2. Delete a linked listEasy
3. Split a linked list into two lists where each list contains alternating elements from itMedium
4. Construct a linked list by merging alternate nodes of two given listsEasy
5. Merge two sorted linked lists into oneMedium
6. Efficiently merge k sorted linked listsHard
7. Reverse a Linked List – Recursive SolutionHard
8. Reverse every group of k nodes in a linked listMedium
9. Find k’th node from the end of a linked listEasy
10. Merge alternate nodes of two linked lists into the first listMedium
11. Delete every N nodes in a linked list after skipping M nodesEasy
12. Rearrange linked list in a specific manner in linear timeMedium
13. Check if a linked list is palindrome or notMedium
14. Move the last node to the front of a linked listEasy
15. Rearrange a linked list by separating odd nodes from even onesMedium
16. Recursively check if the linked list of characters is palindrome or notMedium
17. Add a single-digit number to a linked list representing a numberMedium
18. Reverse every alternate group of k nodes in a linked listMedium
19. Determine whether a linked list is palindrome or notMedium
20. Reverse a doubly linked listEasy
21. Pairwise swap adjacent nodes of a linked listMedium
22. Flatten a Linked ListHard
23. Check if a linked list of strings is palindromicEasy
24. Flatten a multilevel linked listMedium
25. Clone a linked list with random pointerHard
26. Update random pointer for each linked list node to point to the maximum nodeMedium

Sorting:

1. Insertion Sort AlgorithmEasy
2. Selection Sort AlgorithmEasy
3. Bubble Sort AlgorithmEasy
4. Merge Sort AlgorithmEasy
5. Quicksort AlgorithmMedium
6. Hybrid QuickSort AlgorithmMedium
7. Quicksort using Dutch National Flag AlgorithmMedium
8. Quicksort algorithm using Hoare’s partitioning schemeMedium
9. Heap Sort AlgorithmMedium
10. Introsort Algorithm – Overview and C++ ImplementationHard
11. Merge sort algorithm for a singly linked listHard
12. Sort a doubly-linked list using merge sortMedium
13. Inversion count of an arrayHard
14. Find surpasser count for each array elementHard
15. Water Jugs ProblemHard

Binary Tree:

1. Inorder Tree TraversalMedium
2. Preorder Tree TraversalMedium
3. Postorder Tree TraversalMedium
4. Check if two binary trees are identical or notEasy
5. Print bottom view of a binary treeMedium
6. Print top view of a binary treeMedium
7. In-place convert a binary tree to its sum treeEasy
8. Determine whether the given binary tree nodes are cousins of each otherMedium
9. Print cousins of a given node in a binary treeMedium
10. Check if a binary tree is a sum tree or notMedium
11. Combinations of words formed by replacing given numbers with corresponding alphabetsHard
12. Determine whether a binary tree is a subtree of another binary treeMedium
13. Find the diameter of a binary treeMedium
14. Check if a binary tree is symmetric or notEasy
15. Convert a binary tree to its mirrorEasy
16. Determine if a binary tree can be converted to another by doing any number of swaps of childrenEasy
17. Find the Lowest Common Ancestor (LCA) of two nodes in a binary treeMedium
18. Print all paths from the root to leaf nodes of a binary treeEasy
19. Find ancestors of a given node in a binary treeMedium
20. Find distance between given pairs of nodes in a binary treeHard
21. Find the diagonal sum of a binary treeMedium
22. Sink nodes containing zero to the bottom of a binary treeHard
23. Convert a binary tree to a full tree by removing half nodesMedium
24. Truncate a binary tree to remove nodes that lie on a path having a sum less than kMedium
25. Find maximum sum root to leaf path in a binary treeMedium
26. Check if a binary tree is height-balanced or notMedium
27. Convert binary tree to Left-child right-sibling binary treeMedium
28. Print all paths from leaf to root node of a binary treeMedium
29. Find all nodes at a given distance from leaf nodes in a binary treeHard
30. Count all subtrees having the same value of nodes in a binary treeMedium
31. Find the maximum difference between a node and its descendants in a binary treeMedium
32. Find the maximum sum path between two leaves in a binary treeHard
33. Construct a binary tree from inorder and preorder traversalHard
34. Construct a binary tree from inorder and postorder traversalsHard
35. Construct a binary tree from inorder and level order sequenceHard
36. Construct a full binary tree from the preorder sequence with leaf node informationHard
37. Construct a full binary tree from a preorder and postorder sequenceHard
38. Find postorder traversal of a binary tree from its inorder and preorder sequenceMedium
39. Set next pointer to the inorder successor of all nodes in a binary treeEasy
40. Find preorder traversal of a binary tree from its inorder and postorder sequenceHard
41. Find difference between sum of all nodes present at odd and even levels in a binary treeEasy
42. Clone a binary tree with random pointersHard
43. Threaded Binary Tree – Overview and ImplementationMedium
44. Determine if a binary tree satisfies the height-balanced property of a red–black treeMedium
45. Construct an ancestor matrix from a binary treeEasy
46. Find all possible binary trees having the same inorder traversalHard
47. Perform boundary traversal on a binary treeMedium
48. Check if each node of a binary tree has exactly one childEasy
49. Evaluate a Binary Expression TreeEasy
50. Construction of an expression treeEasy
51. Fix children-sum property in a binary treeMedium
52. Maximum path sum in a binary treeHard
53. Create a mirror of an m–ary treeEasy
54. Print a two-dimensional view of a binary treeEasy
55. Construct a Cartesian tree from an inorder traversalMedium
56. Calculate the height of a binary tree with leaf nodes forming a circular doubly linked listMedium
57. Link nodes present in each level of a binary tree in the form of a linked listHard
58. Convert a ternary tree to a doubly-linked listMedium
59. Extract leaves of a binary tree into a doubly-linked listMedium
60. Find the vertical sum of a binary treeHard
61. In-place convert a binary tree to a doubly-linked listHard
62. Check whether the leaf traversal of given binary trees is the same or notHard
63. Efficiently print all nodes between two given levels in a binary treeEasy
64. Calculate the height of a binary treeEasy
65. Delete a binary treeEasy
66. Level order traversal of a binary treeEasy
67. Spiral order traversal of a binary treeMedium
68. Reverse level order traversal of a binary treeEasy
69. Print left view of a binary treeEasy
70. Find the next node at the same level as the given node in a binary treeMedium
71. Check if a binary tree is a complete binary tree or notMedium
72. Print diagonal traversal of a binary treeMedium
73. Invert Binary TreeEasy
74. Convert a binary tree into a doubly-linked list in spiral orderHard
75. Check if a binary tree is a min-heap or notMedium
76. Invert alternate levels of a perfect binary treeHard
77. Perform vertical traversal of a binary treeMedium
78. Compute the maximum number of nodes at any level in a binary treeEasy
79. Print right view of a binary treeMedium
80. Find the minimum depth of a binary treeEasy
81. Print nodes of a binary tree in vertical orderMedium

Binary Search Tree:

1. Insertion in a BSTEasy
2. Search a given key in BSTEasy
3. Deletion from BST (Binary Search Tree)Medium
4. Construct a balanced BST from the given keysEasy
5. Determine whether a given binary tree is a BST or notMedium
6. Check if the given keys represent the same BSTs or not without building BSTHard
7. Find inorder predecessor for the given key in a BSTMedium
8. Find the Lowest Common Ancestor (LCA) of two nodes in a BSTEasy
9. Find k’th smallest and k’th largest element in a BSTEasy
10. Find floor and ceil in a Binary Search TreeMedium
11. Convert a binary tree to BST by maintaining its original structureMedium
12. Remove nodes from a BST that have keys outside a valid rangeMedium
13. Find a pair with the given sum in a BSTEasy
14. Find k’th smallest node in a Binary Search Tree (BST)Easy
15. Find inorder successor for the given key in a BSTMedium
16. Fix a binary tree that is only one swap away from becoming a BSTHard
17. Update every key in a BST to contain the sum of all greater keysMedium
18. Check if a given sequence represents the preorder traversal of a BSTHard
19. Build a Binary Search Tree from a postorder sequenceHard
20. Build a Binary Search Tree from a preorder sequenceHard
21. Count subtrees in a BST whose nodes lie within a given rangeMedium
22. Find the size of the largest BST in a binary treeHard
23. Print complete Binary Search Tree (BST) in increasing orderEasy
24. Print binary tree structure with its contents in C++Medium
25. Treap Data StructureBeginner
26. Implementation of Treap Data Structure (Insert, Search, and Delete)Hard
27. Merge two BSTs into a doubly-linked list in sorted orderHard
28. Construct a height-balanced BST from an unbalanced BSTHard
29. Construct a height-balanced BST from a sorted doubly linked listHard
30. Find a triplet with the given sum in a BSTHard
31. Convert a Binary Search Tree into a Min HeapHard

Dynamic Programming:

1. Longest Common Subsequence ProblemMedium
2. Longest Common Subsequence of k–sequencesMedium
3. Longest Common Subsequence | Finding all LCSHard
4. Longest Palindromic Subsequence using Dynamic ProgrammingMedium
5. Longest Repeated Subsequence ProblemMedium
6. Implement Diff UtilityMedium
7. Shortest Common Supersequence ProblemMedium
8. Shortest Common Supersequence | Finding all SCSHard
9. Shortest Common Supersequence Problem using LCSHard
10. Longest Increasing Subsequence using Dynamic ProgrammingHard
11. Longest Decreasing Subsequence ProblemHard
12. Maximum Sum Increasing Subsequence ProblemMedium
13. The Levenshtein distance (Edit distance) ProblemMedium
14. Find the size of the largest square submatrix of 1’s present in a binary matrixMedium
15. Matrix Chain Multiplication using Dynamic ProgrammingHard
16. Find minimum cost to reach the last cell of a matrix from its first cellMedium
17. Find the longest sequence formed by adjacent numbers in the matrixMedium
18. Count the number of paths in a matrix with a given cost to reach the destination cellMedium
19. 0–1 Knapsack ProblemMedium
20. Partition Problem using Dynamic ProgrammingMedium
21. Subset Sum Problem – Dynamic Programming SolutionMedium
22. 3–Partition ProblemMedium
23. Minimum Sum Partition ProblemHard
24. Rod Cutting ProblemMedium
25. Maximum Product Rod CuttingMedium
26. Coin change-making problemMedium
27. Coin Change ProblemHard
28. Total possible solutions to a linear equation of k variablesHard
29. Longest Alternating Subsequence ProblemMedium
30. Count the number of times a pattern appears in a given string as a subsequenceHard
31. Collect maximum points in a matrix by satisfying given constraintsHard
32. Find all N-digit binary strings without any consecutive 1’sEasy
33. Count total possible combinations of n-digit numbers in a mobile keypadMedium
34. Word Break Problem – Dynamic ProgrammingHard
35. Check if a string is k–palindrome or notHard
36. Find total ways to achieve a given sum with n throws of dice having k facesMedium
37. Wildcard Pattern MatchingHard
38. Find the number of ways to fill an N × 4 matrix with 1 × 4 tilesMedium
39. Ways to reach the bottom-right corner of a matrix with exactly k turns allowedHard
40. Weighted Interval Scheduling ProblemMedium
41. Find total ways to reach n’th stair with at-most m stepsMedium
42. Find total ways to reach the n’th stair from the bottomMedium
43. Find the minimum number of deletions required to convert a string into a palindromeMedium
44. Pots of Gold Game Problem using Dynamic ProgrammingHard
45. Find minimum cuts needed for the palindromic partition of a stringHard
46. Find minimum jumps required to reach the destinationMedium
47. Find the probability that a person is alive after taking n steps on an islandMedium
48. Longest Increasing Subsequence using LCSMedium
49. Count all paths in a matrix from the first cell to the last cellEasy
50. Check if a string matches with the given wildcard patternHard
51. Check if a string is interleaving of two other given stringsMedium
52. Find all employees who directly or indirectly reports to a managerHard
53. Find optimal cost to construct a binary search treeHard
54. Find the maximum sum of a subsequence with no adjacent elementsMedium
55. Minimum-weight triangulation of a convex polygonHard
56. Find maximum profit that can be earned by conditionally selling stocksEasy
57. Program to find n’th Fibonacci numberEasy
58. Count decodings of a given sequence of digitsMedium
59. Hat Check Problem – Counting DerangementsMedium
60. Maximum Independent Set ProblemMedium
61. Find the minimum number of squares that sum to a given numberMedium
62. Truncate an integer array such that 2×min becomes more than maxHard
63. Find ways to calculate a target from elements of the specified arrayMedium
64. Find the length of the longest path in a matrix with consecutive charactersMedium
65. Collect maximum value of coins in a matrixHard
66. Single-Source Shortest Paths – Bellman–Ford AlgorithmMedium
67. All-Pairs Shortest Paths – Floyd Warshall AlgorithmEasy

Programming Puzzles:

1. Implement power function without using multiplication and division operatorsEasy
2. Print all numbers between 1 to N without using a semicolonMedium
3. Determine the if condition to print the specific outputEasy
4. Tower of Hanoi ProblemMedium
5. Print all numbers between 1 to N without using any loop | 4 methodsEasy
6. Multiply two numbers without using a multiplication operator or loopsEasy
7. Find minimum number without using conditional statement or ternary operatorMedium
8. Perform division of two numbers without using division operatorMedium
9. Find maximum number without using conditional statement or ternary operatorEasy

Graphs:

1. Depth First Search (DFS)Medium
2. Breadth-First Search (BFS)Medium
3. Arrival and departure time of vertices in DFSEasy
4. Determine whether a graph is Bipartite using DFSMedium
5. Topological Sort Algorithm for DAGMedium
6. Transitive closure of a graphEasy
7. Determine whether an undirected graph is a tree (Acyclic Connected Graph)Medium
8. 2–Edge Connectivity in a graphHard
9. Check if a digraph is a DAG (Directed Acyclic Graph) or notMedium
10. Disjoint–Set Data Structure (Union–Find Algorithm)Medium
11. Check if a graph is strongly connected or notEasy
12. Check if a graph is strongly connected or not using one DFS TraversalHard
13. Union–Find Algorithm for cycle detection in a graphMedium
14. Find the cost of the shortest path in DAG using one pass of Bellman–FordMedium
15. Find all Possible Topological Orderings of a DAGHard
16. Find correct order of alphabets in a given dictionary of ancient originHard
17. Find the longest path in a Directed Acyclic Graph (DAG)Hard
18. Print all k–colorable configurations of a graph (Vertex coloring of a graph)Medium
19. Print all Hamiltonian paths present in a graphHard
20. Kruskal’s Algorithm for finding Minimum Spanning TreeHard
21. Eulerian cycle in directed graphsHard
22. Find root vertex of a graphMedium
23. Check whether an undirected graph is EulerianMedium
24. Check if a set of words can be rearranged to form a circleHard
25. Find itinerary from the given list of departure and arrival airportsEasy
26. Check if an undirected graph contains a cycle or notMedium
27. Compute the least cost path in a weighted digraph using BFSMedium
28. Find the path between given vertices in a directed graphEasy

Stack:

1. Recursive solution to sort a stackHard
2. Reverse a stack using recursionHard
3. Reverse a string using a stack data structureEasy
4. Reverse an array in C++Easy
5. Find all binary strings that can be formed from a wildcard patternMedium
6. Implement a stack using the queue data structureMedium
7. Implement a queue using the stack data structureMedium

Trie:

1. Lexicographic sorting of a given set of keysMedium
2. Find the maximum occurring word in a given set of stringsEasy
3. Find first k maximum occurring words in a given set of stringsMedium
4. Word Break Problem – Using Trie Data StructureMedium
5. Find all words matching a pattern in the given dictionaryMedium
6. Find the shortest unique prefix for every word in an arrayMedium