DSA interview question

Recursive Bubble Sort

Easy · Algorithms · Topics: sorting, recursion

The problem

Your team's style guide for a teaching platform bans loops in the "recursion" chapter's exercises, so the bubble sort example has to be rewritten recursively. The trick is to notice what one pass of bubble sort achieves: it moves the largest element of the first n elements to position n − 1. After that, the problem is just "bubble sort the first n − 1 elements", which is the same problem on a smaller input, exactly the shape recursion needs. It's a good exercise in turning an iterative algorithm's outer loop into recursion without changing what it does.

Example: [13, 46, 24, 52, 20, 9] → [9, 13, 20, 24, 46, 52].

Function signature

void recursiveBubbleSort(vector<int>& a, int n);  // sorts the first n elements; call with a.size()

Test cases

Input `a`	Output	Explanation
`[13, 46, 24, 52, 20, 9]`	`[9, 13, 20, 24, 46, 52]`
`[5, 1, 4, 2, 8]`	`[1, 2, 4, 5, 8]`
`[1, 2, 3]`	`[1, 2, 3]`	One pass with no swaps, then stop
`[4, 3, 2, 1]`	`[1, 2, 3, 4]`	Deepest recursion: n − 1 levels
`[42]`	`[42]`	Base case n ≤ 1
`[]`	`[]`

(Confirm: the outer loop becomes recursion; the inner pass may remain a loop, and a fully recursive version is also shown; the code cross-checks 1,000 random arrays against std::sort.)

How interviewers phrase it

"Implement bubble sort using recursion."
"Convert this iterative algorithm to a recursive one."
Follow-up: "Can you remove the inner loop too?"

Clarifying questions to ask

Should only the outer loop become recursion, or both loops?
How large can n be? (Recursion depth is up to n.)
Ascending order?

Follow-ups to expect

"What's the base case?"
"What does each call guarantee?"
"Can you add the early exit?"
"How do you make the inner pass recursive?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview