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.
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
- 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.
- Arrays and strings. Track the index or interval that defines the remaining work. Check empty inputs and the point where two pointers meet.
- 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.
- 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.
- 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 totalOpen a question in the editor to read its statement and examples. Sign in to practice.
- Print Numbers from 1 to NRecursion · MathBasic
- Print Numbers from N Down to 1Recursion · MathBasic
- Print a Word N TimesRecursionBasic
- Print Even Numbers from 2 to 2NRecursion · MathBasic
- Print Odd Numbers from 2N - 1 Down to 1Recursion · MathBasic
- Sum of First N Natural NumbersRecursion · MathBasic
- Factorial of a NumberRecursion · MathBasic
- Product of First N Odd NumbersRecursion · MathBasic
- Sum of Squares of First N NumbersRecursion · MathBasic
- Sum of Even Numbers from 2 to 2NRecursion · MathBasic
- Power of a Number (aᵇ)Recursion · MathBasic
- Multiply Two Numbers Using AdditionRecursion · MathBasic
- Count Digits of a NumberRecursion · MathBasic
- Sum of Digits of a NumberRecursion · MathBasic
- Product of Digits of a NumberRecursion · MathBasic
- Remainder Using Repeated SubtractionRecursion · MathBasic
- Integer Division Using Repeated SubtractionRecursion · MathBasic
- Greatest Common Divisor (GCD)Recursion · MathBasic
- Print Digits from Left to RightRecursion · MathBasic
- Print Digits from Right to LeftRecursion · MathBasic
- N-th Fibonacci NumberRecursion · MathBasic
- N-th Triangular NumberRecursion · MathBasic
- Check Power of TwoRecursion · MathBasic
- Check Power of ThreeRecursion · MathBasic
- Count Occurrences of a Specific DigitRecursion · MathBasic
- Print Array Elements in Forward OrderRecursion · ArraysBasic
- Print Array Elements in Reverse OrderRecursion · ArraysBasic
- Sum of Array ElementsRecursion · ArraysBasic
- Product of Array ElementsRecursion · ArraysBasic
- Find Maximum Element in an ArrayRecursion · ArraysBasic
- Find Minimum Element in an ArrayRecursion · ArraysBasic
- Linear Search in an ArrayRecursion · ArraysBasic
- Count Occurrences in an ArrayRecursion · ArraysBasic
- Find First Index of an ElementRecursion · ArraysBasic
- Count Even Numbers in an ArrayRecursion · ArraysBasic
- Check if Array is SortedRecursion · ArraysBasic
- Count Negative Numbers in an ArrayRecursion · ArraysBasic
- Length of a StringRecursion · StringsBasic
- Print Characters of a String ForwardRecursion · StringsBasic
- Print Characters of a String in ReverseRecursion · StringsBasic
- Count Vowels in a StringRecursion · StringsBasic
- Count Occurrences of a CharacterRecursion · StringsBasic
- Check if String is a PalindromeRecursion · StringsBasic
- Reverse a StringRecursion · StringsBasic
- Remove All Occurrences of a CharacterRecursion · StringsBasic
- Replace Character in a StringRecursion · StringsBasic
- Count Steps to Reduce to ZeroRecursion · MathBasic
- Check if All Elements are PositiveRecursion · ArraysBasic
- Find Last Index of an ElementRecursion · ArraysBasic
- Check if String Contains Only DigitsRecursion · StringsBasic
- Recursive Binary SearchRecursion · Binary Search · ArraysEasy
- Fast Exponentiation (Binary Exponentiation)Recursion · MathEasy
- Count Ways to Climb StairsRecursion · Math · Dynamic ProgrammingEasy
- Decimal to Binary StringRecursion · MathEasy
- Tower of Hanoi MovesRecursionEasy
- N-th Tribonacci NumberRecursion · MathEasy
- Count Unique Paths in a GridRecursion · Math · Dynamic ProgrammingEasy
- Check SubsequenceRecursion · Strings · Two PointersEasy
- Replace "pi" with "3.14"Recursion · StringsEasy
- Remove Consecutive DuplicatesRecursion · StringsEasy
- Move All 'x' to the EndRecursion · StringsEasy
- String to Integer (Recursive Atoi)Recursion · StringsEasy
- Count Occurrences of SubstringRecursion · StringsEasy
- Pair StarRecursion · StringsEasy
- Check if Array is a PalindromeRecursion · Arrays · Two PointersEasy
- Reverse an Array In-PlaceRecursion · Arrays · Two PointersEasy
- Find All Indices of an ElementRecursion · ArraysEasy
- Check if Array is Strictly IncreasingRecursion · ArraysEasy
- Pascal's Triangle ValueRecursion · MathEasy
- Count Adjacent Duplicate PairsRecursion · ArraysEasy
- Decimal to Octal StringRecursion · MathEasy
- Decimal to Hexadecimal StringRecursion · MathEasy
- Check Balanced ParenthesesRecursion · StringsEasy
- Recursive Bubble SortRecursion · Arrays · SortingEasy
- Digital Root (Recursive Sum of Digits)Recursion · MathEasy
- Recursive Selection SortRecursion · Arrays · SortingEasy
- Recursive Insertion SortRecursion · Arrays · SortingEasy
- Merge Two Sorted Arrays RecursivelyRecursion · Arrays · SortingEasy
- Alternating Sum of ArrayRecursion · ArraysEasy
- Check if Two Arrays are IdenticalRecursion · ArraysEasy
- Generate All Binary Strings of Length NRecursion · StringsEasy
- Count Binary Strings Without Consecutive 1sRecursion · Dynamic ProgrammingEasy
- Generate All Subsequences of a StringRecursion · StringsEasy
- Josephus Problem SurvivorRecursion · MathEasy
- Count Ways to Score Points (1, 2, or 3)Recursion · Dynamic ProgrammingEasy
- Subset Sum ExistenceRecursion · ArraysEasy
- Sum of Digits in an Alphanumeric StringRecursion · StringsEasy
- Greatest Common Divisor of an ArrayRecursion · Math · ArraysEasy
- Valid Palindrome (Ignoring Non-Alphanumeric)Recursion · Strings · Two PointersEasy
- Trace of a Square MatrixRecursion · Arrays · MatrixEasy
- Check Alternating Signs in ArrayRecursion · ArraysEasy
- Print Triangular Asterisk PatternRecursionEasy
- Find First Uppercase LetterRecursion · StringsEasy
- Tiling a 2 × N BoardRecursion · Dynamic ProgrammingEasy
- Recursive Run-Length EncodingRecursion · StringsEasy
- Permutations of a Short StringRecursion · StringsEasy
- First Occurrence via Binary SearchRecursion · Binary Search · ArraysEasy
- Friends Pairing ProblemRecursion · Dynamic Programming · MathEasy
- Generate Balanced Parentheses (N ≤ 3)Recursion · StringsEasy
- Count Subsets with Given SumRecursion · ArraysEasy
- Merge SortRecursion · Arrays · Sorting · Divide and ConquerMedium
- Quick SortRecursion · Arrays · Sorting · Divide and ConquerMedium
- Subsets (Power Set)Recursion · Backtracking · ArraysMedium
- Combinations of Size KRecursion · BacktrackingMedium
- Letter Combinations of a Phone NumberRecursion · Backtracking · StringsMedium
- Permutations of an ArrayRecursion · Backtracking · ArraysMedium
- Subsets II (With Duplicates)Recursion · Backtracking · ArraysMedium
- Combination Sum (Unbounded Reuse)Recursion · Backtracking · ArraysMedium
- Combination Sum II (Single-Use with Duplicates)Recursion · Backtracking · ArraysMedium
- Permutations II (With Duplicates)Recursion · Backtracking · ArraysMedium
- Palindrome PartitioningRecursion · Backtracking · StringsMedium
- Generate Balanced ParenthesesRecursion · Backtracking · StringsMedium
- Decode String (Nested Encodings)Recursion · Strings · StackMedium
- Restore IP AddressesRecursion · Backtracking · StringsMedium
- Different Ways to Add ParenthesesRecursion · Divide and Conquer · MathMedium
- Word Search in a 2D GridRecursion · Backtracking · MatrixMedium
- Flood Fill AlgorithmRecursion · Matrix · Depth-First SearchMedium
- Number of IslandsRecursion · Matrix · Depth-First SearchMedium
- Rat in a Maze (All Paths)Recursion · Backtracking · MatrixMedium
- Max Area of IslandRecursion · Matrix · Depth-First SearchMedium
- Target Sum (+ / - Assignments)Recursion · Dynamic Programming · BacktrackingMedium
- Partition Equal Subset SumRecursion · Dynamic ProgrammingMedium
- 0/1 KnapsackRecursion · Dynamic ProgrammingMedium
- Word BreakRecursion · Dynamic Programming · Hash TableMedium
- Gray Code SequenceRecursion · Math · Bit ManipulationMedium
- Minimum Path Sum in a GridRecursion · Dynamic Programming · MatrixMedium
- Longest Common Subsequence (LCS)Recursion · Dynamic Programming · StringsMedium
- Edit Distance (Levenshtein Distance)Recursion · Dynamic Programming · StringsMedium
- Coin Change (Minimum Coins)Recursion · Dynamic ProgrammingMedium
- House RobberRecursion · Dynamic Programming · ArraysMedium
- Combination Sum IIIRecursion · BacktrackingMedium
- Surrounded RegionsRecursion · Matrix · Depth-First SearchMedium
- Non-Decreasing SubsequencesRecursion · Backtracking · ArraysMedium
- Number of Closed IslandsRecursion · Matrix · Depth-First SearchMedium
- Predict the Winner (Minimax Recursion)Recursion · Game Theory · ArraysMedium
- Path with Maximum GoldRecursion · Backtracking · MatrixMedium
- Beautiful ArrangementRecursion · BacktrackingMedium
- Partition to K Equal Sum SubsetsRecursion · Backtracking · Dynamic ProgrammingMedium
- Split a String Into the Max Number of Unique SubstringsRecursion · Backtracking · StringsMedium
- Fair Distribution of CookiesRecursion · Backtracking · ArraysMedium
- Letter Case PermutationRecursion · Backtracking · StringsMedium
- Additive NumberRecursion · Backtracking · StringsMedium
- The Number of Beautiful SubsetsRecursion · Backtracking · ArraysMedium
- Find Kth Bit in Nth Binary StringRecursion · Divide and Conquer · StringsMedium
- Integer ReplacementRecursion · Dynamic Programming · MathMedium
- K-th Symbol in GrammarRecursion · Divide and Conquer · MathMedium
- Lexicographical NumbersRecursion · Depth-First SearchMedium
- All Paths from Source to Target in a DAGRecursion · Graph · BacktrackingMedium
- Maximum Length of a Concatenated String with Unique CharactersRecursion · Backtracking · StringsMedium
- Matchsticks to SquareRecursion · Backtracking · ArraysMedium
- N-Queens (All Solutions)Recursion · BacktrackingHard
- Sudoku SolverRecursion · Backtracking · MatrixHard
- Expression Add OperatorsRecursion · Backtracking · StringsHard
- Regular Expression MatchingRecursion · Strings · Dynamic ProgrammingHard
- Wildcard MatchingRecursion · Strings · Dynamic Programming · GreedyHard
- Word Search II (Multi-Word Grid Search)Recursion · Backtracking · Trie · MatrixHard
- Word Break II (Reconstruct All Sentences)Recursion · Backtracking · Strings · Dynamic ProgrammingHard
- Remove Invalid ParenthesesRecursion · Backtracking · Strings · Breadth-First SearchHard
- Palindrome Partitioning II (Minimum Cuts)Recursion · Strings · Dynamic ProgrammingHard
- Unique Paths III (Hamiltonian Grid Path)Recursion · Backtracking · Arrays · MatrixHard
- 24 GameRecursion · Backtracking · MathHard
- Knight's TourRecursion · Backtracking · MatrixHard
- Scramble StringRecursion · Strings · Dynamic ProgrammingHard
- Burst Balloons (Interval Divide-and-Conquer)Recursion · Arrays · Dynamic Programming · Divide and ConquerHard
- Frog JumpRecursion · Arrays · Dynamic ProgrammingHard
- Cryptarithmetic Puzzle SolverRecursion · Backtracking · Math · StringsHard
- Maximum Score Words Formed by LettersRecursion · Backtracking · Arrays · StringsHard
- Optimal Account BalancingRecursion · Backtracking · Arrays · Dynamic ProgrammingHard
- Reconstruct ItineraryRecursion · Backtracking · Graph · Depth-First SearchHard
- Word Ladder II (All Shortest Sequences)Recursion · Backtracking · Breadth-First Search · StringsHard
- Stone Game III (Minimax with Multi-Move Choice)Recursion · Math · Dynamic Programming · Game TheoryHard
- Domino and Tromino TilingRecursion · Dynamic ProgrammingHard
- Shortest Superstring LengthRecursion · Backtracking · Strings · Dynamic ProgrammingHard
- Split Array With Same AverageRecursion · Arrays · Math · Dynamic ProgrammingHard
- Minimum Cost to Cut a StickRecursion · Arrays · Dynamic Programming · SortingHard
- Count of Smaller Numbers After SelfRecursion · Arrays · Divide and Conquer · Binary SearchHard
- K-th Element in Two Sorted ArraysRecursion · Arrays · Binary Search · Divide and ConquerHard
- Parsing a Boolean ExpressionRecursion · Strings · StackHard
- Freedom TrailRecursion · Strings · Dynamic ProgrammingHard
- Strange Printer (Interval Recursion)Recursion · Strings · Dynamic ProgrammingHard