DSA Factory
Free lessonsRecursion · Stage 0 · A function that calls itself · Step 2

Reverse a string

Do your part after the smaller call returns, and the answer builds on the way back. About 9 minutes.

Calls wait for each other

When a function calls itself, it pauses and waits, like a manager handing a task to an assistant. The smaller call runs, maybe calls again, and so on down to the base case. Then the calls finish one by one in reverse: the deepest returns first, and each waiting call picks up where it paused.

This pile of paused calls is called the call stack.

Going down: each call hands a smaller problem to the next.
Coming back: each call uses the returned answer and finishes its part.
reverse("cat"), one call at a time
rev("cat")rev("at")rev("t")

reverse("cat") can't answer yet. It asks reverse("at") and waits, holding on to its letter c.

Move 1 of 5

Your part can go after the call

To reverse "cat", reverse the rest, "at", which gives "ta". Then put the first letter, c, at the end: "tac". The smaller call does most of the work, and your part is just placing one letter.

Where you put it, before or after the returned answer, decides the order of the result.

Reverse the rest, then add the first letter last: the first letter goes at the end.
Base case: a string of length 0 or 1 is already its own reverse.
One call per letter: so keep strings short: here at most 500 letters.
In code
def reverse_string(s):
    if len(s) <= 1:
        return s
    return reverse_string(s[1:]) + s[0]
Quick check

reverse("dog") returns reverse("og") + "d". What does reverse("og") return?

  1. A"go"
  2. B"og"
  3. C"g"
Show the answer

"go". reverse("og") is reverse("g") + "o" = "g" + "o". So the full answer is "go" + "d" = "god".

Your problem

Reverse a string

Return s written backwards. Use recursion: reverse everything after the first letter with a smaller call, then place the first letter where it belongs.

Example
s = "cat" → "tac"

0 ≤ length of s ≤ 500 · letters, digits and spaces · one call per letter, so at most 500 calls deep

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding