Get started

Recursion Coding Problems: 9 Questions with Solutions

9 recursion coding problems — 3 easy · 3 medium · 3 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 6-day plan.

  • Problems: 9
  • By difficulty: 3 easy · 3 medium · 3 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

A function that calls itself on a smaller input. The problems here isolate the two things that make recursion work — a base case that stops it and a step that gets closer to it — on inputs where the recursive statement is the clearest solution, and show where an explicit stack or a loop should replace it.

How recursion works, step by step

power(x, n):if n == 0: return 1h = power(x, n // 2)return h * h if n is even else h * h * xanswer = 1024power(2, 10)returned 10241024
Fast power by halving, with recursion. Example: power(2, 10)
  1. power(2, 10) computes 2 to the 10th by halving: with h = power(x, n // 2), the answer is h * h, times one more x when n is odd. The first call cannot finish until power(2, 5) answers, so it waits on the call stack.
  2. power(2, 5) is pushed on top and asks for power(2, 2). Each call keeps its own n, so the call below it still remembers where it was; n halves every time, so the stack grows like log n.
  3. power(2, 2) is pushed on top and asks for power(2, 1). Each call keeps its own n, so the 2 calls below it still remember where they were; n halves every time, so the stack grows like log n.
  4. power(2, 1) is pushed on top and asks for power(2, 0). Each call keeps its own n, so the 3 calls below it still remember where they were; n halves every time, so the stack grows like log n.
  5. power(2, 0) hits the base case and returns 1 without calling anything: this is what stops the recursion. The stack is 5 calls deep, its deepest point.
  6. power(2, 0) is popped and passes 1 back up. power(2, 1) resumes with h = 1; n = 1 is odd, so it returns 1 * 1 * 2 = 2.
  7. power(2, 1) is popped and passes 2 back up. power(2, 2) resumes with h = 2; n = 2 is even, so it returns 2 * 2 = 4.
  8. power(2, 2) is popped and passes 4 back up. power(2, 5) resumes with h = 4; n = 5 is odd, so it returns 4 * 4 * 2 = 32.
  9. power(2, 5) is popped and passes 32 back up. power(2, 10) resumes with h = 32; n = 10 is even, so it returns 32 * 32 = 1024.
  10. power(2, 10) passes 1024 back to its caller and the stack empties. It took 5 calls where a loop would multiply 10 times: O(log n) calls and O(log n) stack space, because n halves on every call.

Recursion study plan

All 9 Recursion problems (3 easy, 3 medium and 3 hard) over 6 days, about 5 h 30 min in all — the pattern first, then easiest to hardest. Then move on to Merge Sort.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 5

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 6

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Merge Sort

Recursion: the essentials

When to reach for it

The problem is defined by a smaller copy of itself: nested structure (3[a2[c]]), a value given by a recurrence (Fibonacci, powers), a number reduced by a fixed step (is n a power of three? Divide by 3 and ask again), a choice repeated at every position. If you can say "the answer for n is built from the answer for something smaller", that sentence is the function.

The pattern

Trust the recursive call: assume it returns the right answer for the smaller input and write only how to build this answer from it. Then check that the base case catches every input the step can reach — including 0, 1, the empty input and negatives. If the same arguments come back again and again, memoise.

def power(x, n):                    # x to the n, n >= 0, in O(log n) calls
    if n == 0:
        return 1
    half = power(x, n // 2)
    return half * half if n % 2 == 0 else half * half * x

Cost

Time is the number of calls times the work per call. Space is the maximum depth, since every pending call holds a stack frame. Naive Fibonacci makes O(φⁿ) calls, about 1.6ⁿ; memoised, it makes O(n).

Common mistakes

  • A base case some inputs step past: n == 0 when n can be negative, or a step of 2 that jumps over it.
  • Making the same call twice, as in power(x, n // 2) * power(x, n // 2), which turns O(log n) calls into O(n).
  • Running out of stack: Python stops at 1,000 frames by default, so recursion over a 10⁵-long input needs a loop or an explicit stack.
  • Slicing or concatenating at every level, a hidden O(n) per call.

Start with

All recursion problems

Easy (3)

Medium (3)

Hard (3)

Companies that ask recursion problems

  • Amazon 7 problems on recursion
  • Google 5 problems on recursion
  • Microsoft 3 problems on recursion
  • Adobe 2 problems on recursion
  • Accenture 1 problem on recursion
  • Hulu 1 problem on recursion
  • Infosys 1 problem on recursion
  • Meta 1 problem on recursion
  • TCS 1 problem on recursion
  • Wipro 1 problem on recursion

Next topic: Merge Sort