Reversing a string with recursion

Reversing ABC gives CBA. A loop can do that easily, but the problem is a good small example of how to think recursively: describe the answer for a word in terms of the answer for a shorter word, and give the answer for the smallest word directly. Type a word of up to 10 characters and press Reverse.

The idea

Split the word into its first character and the rest. The reversed word is the rest, reversed, followed by the first character: reverse("ABC") = reverse("BC") + "A". The rest is shorter, so after enough steps we reach the empty word, whose reverse is itself. That is the base case, and it is what stops the recursion.

Four stacked frames: reverse("ABC") calls reverse("BC"), which calls reverse("C"), which calls the base case reverse("") returning the empty string; going back up, reverse("C") returns "C", reverse("BC") returns "C" + "B" = "CB", and reverse("ABC") returns "CB" + "A" = "CBA"
Each call waits for the shorter word's answer, then appends its own first character; the answers are built on the way back up.
def reverse(word):
    if (word == ""):
        return word                      # base case: nothing to reverse
    else:
        subProblem  = word[1:]           # everything except the first character
        subSolution = reverse(subProblem)
        solution    = subSolution + word[0]
        return solution

(The last line on the canvas reads return = solution; it simply means return solution.)

What the canvas shows

The line being executed is red. Each call gets an activation record (a stack frame), drawn as a box with the call's own four variables: word, subProblem, subSolution and solution. A new call's box appears below its caller's; if the stack gets too tall, it continues in the next column. When a call returns, its box disappears and "Return Value = ..." briefly shows the value handed back to the caller, which stores it in its subSolution field. The final answer is printed below the code.

Worked example: reverse("ABC")

The calls go down until the base case, then the answers are built on the way back up:

step  what happens                                         stack (top of stack last)
 1    reverse("ABC"): subProblem = "BC", calls down        reverse("ABC")
 2    reverse("BC"):  subProblem = "C",  calls down        reverse("ABC"), reverse("BC")
 3    reverse("C"):   subProblem = "",   calls down        ..., reverse("BC"), reverse("C")
 4    reverse(""):    base case, returns ""                ..., reverse("C"), reverse("")
 5    reverse("C"):   subSolution = "",   solution = "" + "C"  = "C",   returns "C"
 6    reverse("BC"):  subSolution = "C",  solution = "C" + "B" = "CB",  returns "CB"
 7    reverse("ABC"): subSolution = "CB", solution = "CB" + "A" = "CBA", returns "CBA"

At its deepest (step 4) there are four frames on the stack, one for each of "ABC", "BC", "C" and "". Each frame waits, with its own word, until the call below it returns; that is why every frame can still use its own word[0] after the recursive call.

Why it is correct

By induction on the length of the word. The empty word is its own reverse, so the base case is right. For a word w = cr (first character c, rest r), assume reverse(r) is right, since r is shorter. The reverse of cr reads the characters of r from last to first and then c, which is exactly reverse(r) + c. Every call makes the word one character shorter, so the base case is always reached.

Running time and space

A word of length n causes n + 1 calls, and the recursion is n + 1 frames deep. But each call copies strings: word[1:] builds a new string of length k − 1 and the concatenation builds one of length k. Summed over all calls that is 1 + 2 + ... + n, so the total time is Θ(n2), and the strings held by the frames on the stack also add up to Θ(n2) characters. Swapping characters from both ends of an array in a loop reverses it in Θ(n) time and O(1) extra space.

Common mistakes and variants

  • Missing or wrong base case: without it the recursion never stops and the program crashes with a stack overflow. Using only len(word) == 1 as the base case has the same problem for the empty word, since ""[1:] is again "".
  • Wrong order: word[0] + reverse(word[1:]) just rebuilds the original word.
  • Very long input: one frame per character means a string with tens of thousands of characters can exceed the stack limit (Python stops at about 1,000 frames by default).
  • Other splits: reverse(word) = word[-1] + reverse(word[:-1]) works just as well, and splitting in half, reverse(second half) + reverse(first half), gives a recursion only O(log n) deep.
  • Accumulator version: rev(word, acc) = rev(word[1:], word[0] + acc) is tail-recursive, which some languages turn into a loop.

Where it is used

Reversing a string recursively is mainly a teaching example, but the pattern — solve a smaller copy of the problem, then combine it with the leftover piece — is the heart of recursive list processing, reversing a linked list, checking palindromes, and divide-and-conquer algorithms such as merge sort. Watching the stack frames here also explains how every recursive function works under the hood.