DSAWiser

DSA question set · 180 questions

Recursion Practice Questions: Base Cases, Backtracking and DSA

Build recursion skills with DSA practice problems covering base cases, call stacks, backtracking, trees, and dynamic programming. Trace your code in DSAWiser.

RecursionMathArraysStringsBinary SearchDynamic ProgrammingTwo PointersSortingMatrixDivide and ConquerBacktrackingStackDepth-First SearchHash TableBit ManipulationGame TheoryGraphGreedyTrieBreadth-First Search

What you will learn

This collection starts with small recursive functions and extends into backtracking, tree traversal, and dynamic programming. The same three questions guide each problem: what stops the recursion, how does the input become smaller, and what must happen when a call returns?

Begin with printing or counting problems to separate the order of calls from the order of output. Then use sums and factorials to see how return values travel back through the call stack. Branching problems introduce choices, while backtracking adds the need to undo a choice before trying another branch.

Prerequisites

You should understand functions, conditional statements, array and string indexing, and basic loops. Before attempting the tree and graph problems, review their representations: children or neighbours determine the next recursive calls, and a visited set may be needed to avoid revisiting states.

Work through the collection in stages

  1. Single recursive calls. Start with printing numbers, summing natural numbers, and factorials. Write the smallest valid input and its expected result before writing the recursive step.
  2. Arrays and strings. Track the index or interval that defines the remaining work. Check empty inputs and the point where two pointers meet.
  3. Branching and backtracking. Draw the choices for a small input. Identify which state is shared, when it changes, and when it must be restored. Subsets and permutations are useful exercises for this distinction.
  4. Trees and depth-first search. State what one call promises to compute for its subtree or connected region. Check whether work belongs before the child calls, between them, or after them.
  5. Repeated subproblems. Look for calls with the same arguments in problems such as Fibonacci, coin change, or longest common subsequence. Define the state clearly before adding memoization.

The question list preserves the collection’s order. If a later topic is unfamiliar, return to a smaller problem with the same call structure before proceeding.

Trace calls and returns separately

Use the code visualizer with a small input first. Predict the arguments of the next call, the depth of the stack, and the value returned to its caller. For backtracking, also predict the shared state immediately after a recursive call finishes.

Do not infer running time from recursion depth alone. A shallow function can still make many calls when it branches. Count both the number of states visited and the work done in each state; distinguish total work from the maximum number of simultaneously active calls.

Check these common mistakes

  • A base case that stops too early or fails to cover the smallest valid input.
  • A recursive step that leaves the input unchanged and never makes progress.
  • Forgetting to return a recursive result to the caller.
  • Keeping a mutable choice after returning from a backtracking branch.
  • Memoizing with an incomplete key when several arguments define the state.

For each solution, explain the base case and the progress rule, then verify both with the editor’s examples before trying larger inputs.

Questions in this set

180 total

Open a question in the editor to read its statement and examples. Sign in to practice.

  1. Print Numbers from 1 to NRecursion · MathBasic
  2. Print Numbers from N Down to 1Recursion · MathBasic
  3. Print a Word N TimesRecursionBasic
  4. Print Even Numbers from 2 to 2NRecursion · MathBasic
  5. Print Odd Numbers from 2N - 1 Down to 1Recursion · MathBasic
  6. Sum of First N Natural NumbersRecursion · MathBasic
  7. Factorial of a NumberRecursion · MathBasic
  8. Product of First N Odd NumbersRecursion · MathBasic
  9. Sum of Squares of First N NumbersRecursion · MathBasic
  10. Sum of Even Numbers from 2 to 2NRecursion · MathBasic
  11. Power of a Number (aᵇ)Recursion · MathBasic
  12. Multiply Two Numbers Using AdditionRecursion · MathBasic
  13. Count Digits of a NumberRecursion · MathBasic
  14. Sum of Digits of a NumberRecursion · MathBasic
  15. Product of Digits of a NumberRecursion · MathBasic
  16. Remainder Using Repeated SubtractionRecursion · MathBasic
  17. Integer Division Using Repeated SubtractionRecursion · MathBasic
  18. Greatest Common Divisor (GCD)Recursion · MathBasic
  19. Print Digits from Left to RightRecursion · MathBasic
  20. Print Digits from Right to LeftRecursion · MathBasic
  21. N-th Fibonacci NumberRecursion · MathBasic
  22. N-th Triangular NumberRecursion · MathBasic
  23. Check Power of TwoRecursion · MathBasic
  24. Check Power of ThreeRecursion · MathBasic
  25. Count Occurrences of a Specific DigitRecursion · MathBasic
  26. Print Array Elements in Forward OrderRecursion · ArraysBasic
  27. Print Array Elements in Reverse OrderRecursion · ArraysBasic
  28. Sum of Array ElementsRecursion · ArraysBasic
  29. Product of Array ElementsRecursion · ArraysBasic
  30. Find Maximum Element in an ArrayRecursion · ArraysBasic
  31. Find Minimum Element in an ArrayRecursion · ArraysBasic
  32. Linear Search in an ArrayRecursion · ArraysBasic
  33. Count Occurrences in an ArrayRecursion · ArraysBasic
  34. Find First Index of an ElementRecursion · ArraysBasic
  35. Count Even Numbers in an ArrayRecursion · ArraysBasic
  36. Check if Array is SortedRecursion · ArraysBasic
  37. Count Negative Numbers in an ArrayRecursion · ArraysBasic
  38. Length of a StringRecursion · StringsBasic
  39. Print Characters of a String ForwardRecursion · StringsBasic
  40. Print Characters of a String in ReverseRecursion · StringsBasic
  41. Count Vowels in a StringRecursion · StringsBasic
  42. Count Occurrences of a CharacterRecursion · StringsBasic
  43. Check if String is a PalindromeRecursion · StringsBasic
  44. Reverse a StringRecursion · StringsBasic
  45. Remove All Occurrences of a CharacterRecursion · StringsBasic
  46. Replace Character in a StringRecursion · StringsBasic
  47. Count Steps to Reduce to ZeroRecursion · MathBasic
  48. Check if All Elements are PositiveRecursion · ArraysBasic
  49. Find Last Index of an ElementRecursion · ArraysBasic
  50. Check if String Contains Only DigitsRecursion · StringsBasic
  51. Recursive Binary SearchRecursion · Binary Search · ArraysEasy
  52. Fast Exponentiation (Binary Exponentiation)Recursion · MathEasy
  53. Count Ways to Climb StairsRecursion · Math · Dynamic ProgrammingEasy
  54. Decimal to Binary StringRecursion · MathEasy
  55. Tower of Hanoi MovesRecursionEasy
  56. N-th Tribonacci NumberRecursion · MathEasy
  57. Count Unique Paths in a GridRecursion · Math · Dynamic ProgrammingEasy
  58. Check SubsequenceRecursion · Strings · Two PointersEasy
  59. Replace "pi" with "3.14"Recursion · StringsEasy
  60. Remove Consecutive DuplicatesRecursion · StringsEasy
  61. Move All 'x' to the EndRecursion · StringsEasy
  62. String to Integer (Recursive Atoi)Recursion · StringsEasy
  63. Count Occurrences of SubstringRecursion · StringsEasy
  64. Pair StarRecursion · StringsEasy
  65. Check if Array is a PalindromeRecursion · Arrays · Two PointersEasy
  66. Reverse an Array In-PlaceRecursion · Arrays · Two PointersEasy
  67. Find All Indices of an ElementRecursion · ArraysEasy
  68. Check if Array is Strictly IncreasingRecursion · ArraysEasy
  69. Pascal's Triangle ValueRecursion · MathEasy
  70. Count Adjacent Duplicate PairsRecursion · ArraysEasy
  71. Decimal to Octal StringRecursion · MathEasy
  72. Decimal to Hexadecimal StringRecursion · MathEasy
  73. Check Balanced ParenthesesRecursion · StringsEasy
  74. Recursive Bubble SortRecursion · Arrays · SortingEasy
  75. Digital Root (Recursive Sum of Digits)Recursion · MathEasy
  76. Recursive Selection SortRecursion · Arrays · SortingEasy
  77. Recursive Insertion SortRecursion · Arrays · SortingEasy
  78. Merge Two Sorted Arrays RecursivelyRecursion · Arrays · SortingEasy
  79. Alternating Sum of ArrayRecursion · ArraysEasy
  80. Check if Two Arrays are IdenticalRecursion · ArraysEasy
  81. Generate All Binary Strings of Length NRecursion · StringsEasy
  82. Count Binary Strings Without Consecutive 1sRecursion · Dynamic ProgrammingEasy
  83. Generate All Subsequences of a StringRecursion · StringsEasy
  84. Josephus Problem SurvivorRecursion · MathEasy
  85. Count Ways to Score Points (1, 2, or 3)Recursion · Dynamic ProgrammingEasy
  86. Subset Sum ExistenceRecursion · ArraysEasy
  87. Sum of Digits in an Alphanumeric StringRecursion · StringsEasy
  88. Greatest Common Divisor of an ArrayRecursion · Math · ArraysEasy
  89. Valid Palindrome (Ignoring Non-Alphanumeric)Recursion · Strings · Two PointersEasy
  90. Trace of a Square MatrixRecursion · Arrays · MatrixEasy
  91. Check Alternating Signs in ArrayRecursion · ArraysEasy
  92. Print Triangular Asterisk PatternRecursionEasy
  93. Find First Uppercase LetterRecursion · StringsEasy
  94. Tiling a 2 × N BoardRecursion · Dynamic ProgrammingEasy
  95. Recursive Run-Length EncodingRecursion · StringsEasy
  96. Permutations of a Short StringRecursion · StringsEasy
  97. First Occurrence via Binary SearchRecursion · Binary Search · ArraysEasy
  98. Friends Pairing ProblemRecursion · Dynamic Programming · MathEasy
  99. Generate Balanced Parentheses (N ≤ 3)Recursion · StringsEasy
  100. Count Subsets with Given SumRecursion · ArraysEasy
  101. Merge SortRecursion · Arrays · Sorting · Divide and ConquerMedium
  102. Quick SortRecursion · Arrays · Sorting · Divide and ConquerMedium
  103. Subsets (Power Set)Recursion · Backtracking · ArraysMedium
  104. Combinations of Size KRecursion · BacktrackingMedium
  105. Letter Combinations of a Phone NumberRecursion · Backtracking · StringsMedium
  106. Permutations of an ArrayRecursion · Backtracking · ArraysMedium
  107. Subsets II (With Duplicates)Recursion · Backtracking · ArraysMedium
  108. Combination Sum (Unbounded Reuse)Recursion · Backtracking · ArraysMedium
  109. Combination Sum II (Single-Use with Duplicates)Recursion · Backtracking · ArraysMedium
  110. Permutations II (With Duplicates)Recursion · Backtracking · ArraysMedium
  111. Palindrome PartitioningRecursion · Backtracking · StringsMedium
  112. Generate Balanced ParenthesesRecursion · Backtracking · StringsMedium
  113. Decode String (Nested Encodings)Recursion · Strings · StackMedium
  114. Restore IP AddressesRecursion · Backtracking · StringsMedium
  115. Different Ways to Add ParenthesesRecursion · Divide and Conquer · MathMedium
  116. Word Search in a 2D GridRecursion · Backtracking · MatrixMedium
  117. Flood Fill AlgorithmRecursion · Matrix · Depth-First SearchMedium
  118. Number of IslandsRecursion · Matrix · Depth-First SearchMedium
  119. Rat in a Maze (All Paths)Recursion · Backtracking · MatrixMedium
  120. Max Area of IslandRecursion · Matrix · Depth-First SearchMedium
  121. Target Sum (+ / - Assignments)Recursion · Dynamic Programming · BacktrackingMedium
  122. Partition Equal Subset SumRecursion · Dynamic ProgrammingMedium
  123. 0/1 KnapsackRecursion · Dynamic ProgrammingMedium
  124. Word BreakRecursion · Dynamic Programming · Hash TableMedium
  125. Gray Code SequenceRecursion · Math · Bit ManipulationMedium
  126. Minimum Path Sum in a GridRecursion · Dynamic Programming · MatrixMedium
  127. Longest Common Subsequence (LCS)Recursion · Dynamic Programming · StringsMedium
  128. Edit Distance (Levenshtein Distance)Recursion · Dynamic Programming · StringsMedium
  129. Coin Change (Minimum Coins)Recursion · Dynamic ProgrammingMedium
  130. House RobberRecursion · Dynamic Programming · ArraysMedium
  131. Combination Sum IIIRecursion · BacktrackingMedium
  132. Surrounded RegionsRecursion · Matrix · Depth-First SearchMedium
  133. Non-Decreasing SubsequencesRecursion · Backtracking · ArraysMedium
  134. Number of Closed IslandsRecursion · Matrix · Depth-First SearchMedium
  135. Predict the Winner (Minimax Recursion)Recursion · Game Theory · ArraysMedium
  136. Path with Maximum GoldRecursion · Backtracking · MatrixMedium
  137. Beautiful ArrangementRecursion · BacktrackingMedium
  138. Partition to K Equal Sum SubsetsRecursion · Backtracking · Dynamic ProgrammingMedium
  139. Split a String Into the Max Number of Unique SubstringsRecursion · Backtracking · StringsMedium
  140. Fair Distribution of CookiesRecursion · Backtracking · ArraysMedium
  141. Letter Case PermutationRecursion · Backtracking · StringsMedium
  142. Additive NumberRecursion · Backtracking · StringsMedium
  143. The Number of Beautiful SubsetsRecursion · Backtracking · ArraysMedium
  144. Find Kth Bit in Nth Binary StringRecursion · Divide and Conquer · StringsMedium
  145. Integer ReplacementRecursion · Dynamic Programming · MathMedium
  146. K-th Symbol in GrammarRecursion · Divide and Conquer · MathMedium
  147. Lexicographical NumbersRecursion · Depth-First SearchMedium
  148. All Paths from Source to Target in a DAGRecursion · Graph · BacktrackingMedium
  149. Maximum Length of a Concatenated String with Unique CharactersRecursion · Backtracking · StringsMedium
  150. Matchsticks to SquareRecursion · Backtracking · ArraysMedium
  151. N-Queens (All Solutions)Recursion · BacktrackingHard
  152. Sudoku SolverRecursion · Backtracking · MatrixHard
  153. Expression Add OperatorsRecursion · Backtracking · StringsHard
  154. Regular Expression MatchingRecursion · Strings · Dynamic ProgrammingHard
  155. Wildcard MatchingRecursion · Strings · Dynamic Programming · GreedyHard
  156. Word Search II (Multi-Word Grid Search)Recursion · Backtracking · Trie · MatrixHard
  157. Word Break II (Reconstruct All Sentences)Recursion · Backtracking · Strings · Dynamic ProgrammingHard
  158. Remove Invalid ParenthesesRecursion · Backtracking · Strings · Breadth-First SearchHard
  159. Palindrome Partitioning II (Minimum Cuts)Recursion · Strings · Dynamic ProgrammingHard
  160. Unique Paths III (Hamiltonian Grid Path)Recursion · Backtracking · Arrays · MatrixHard
  161. 24 GameRecursion · Backtracking · MathHard
  162. Knight's TourRecursion · Backtracking · MatrixHard
  163. Scramble StringRecursion · Strings · Dynamic ProgrammingHard
  164. Burst Balloons (Interval Divide-and-Conquer)Recursion · Arrays · Dynamic Programming · Divide and ConquerHard
  165. Frog JumpRecursion · Arrays · Dynamic ProgrammingHard
  166. Cryptarithmetic Puzzle SolverRecursion · Backtracking · Math · StringsHard
  167. Maximum Score Words Formed by LettersRecursion · Backtracking · Arrays · StringsHard
  168. Optimal Account BalancingRecursion · Backtracking · Arrays · Dynamic ProgrammingHard
  169. Reconstruct ItineraryRecursion · Backtracking · Graph · Depth-First SearchHard
  170. Word Ladder II (All Shortest Sequences)Recursion · Backtracking · Breadth-First Search · StringsHard
  171. Stone Game III (Minimax with Multi-Move Choice)Recursion · Math · Dynamic Programming · Game TheoryHard
  172. Domino and Tromino TilingRecursion · Dynamic ProgrammingHard
  173. Shortest Superstring LengthRecursion · Backtracking · Strings · Dynamic ProgrammingHard
  174. Split Array With Same AverageRecursion · Arrays · Math · Dynamic ProgrammingHard
  175. Minimum Cost to Cut a StickRecursion · Arrays · Dynamic Programming · SortingHard
  176. Count of Smaller Numbers After SelfRecursion · Arrays · Divide and Conquer · Binary SearchHard
  177. K-th Element in Two Sorted ArraysRecursion · Arrays · Binary Search · Divide and ConquerHard
  178. Parsing a Boolean ExpressionRecursion · Strings · StackHard
  179. Freedom TrailRecursion · Strings · Dynamic ProgrammingHard
  180. Strange Printer (Interval Recursion)Recursion · Strings · Dynamic ProgrammingHard