Introduction

The recursive edit-distance algorithm described in Skiena's treatment is the direct formulation of the Levenshtein distance recurrence. It is elegant because it mirrors the definition of the problem, but the plain recursive version is exponentially slow unless you add memoization or convert it to dynamic programming.

The Recursive Recurrence

Edit distance asks for the minimum number of insertions, deletions, and substitutions needed to turn one string into another.

Let dist(i, j) be the edit distance between the first i characters of one string and the first j characters of the other. Then:

• if i == 0, the answer is j
• if j == 0, the answer is i
• if the last characters match, recurse on dist(i - 1, j - 1)
• otherwise take 1 + min(insert, delete, substitute)

That recurrence is the core of the algorithm.

A Plain Recursive Implementation

1def edit_distance_recursive(a, b, i=None, j=None):
2    if i is None:
3        i = len(a)
4    if j is None:
5        j = len(b)
6
7    if i == 0:
8        return j
9    if j == 0:
10        return i
11
12    if a[i - 1] == b[j - 1]:
13        return edit_distance_recursive(a, b, i - 1, j - 1)
14
15    insert_cost = edit_distance_recursive(a, b, i, j - 1)
16    delete_cost = edit_distance_recursive(a, b, i - 1, j)
17    replace_cost = edit_distance_recursive(a, b, i - 1, j - 1)
18
19    return 1 + min(insert_cost, delete_cost, replace_cost)
20
21
22print(edit_distance_recursive("kitten", "sitting"))

Output:

3

This is correct, but it repeats the same subproblems many times.

Why the Plain Recursive Version Is Slow

Consider dist(6, 7) for "kitten" and "sitting". The recursive calls branch into smaller suffix comparisons, but many of those comparisons overlap. The same pair of prefix lengths can be reached through different paths, so the recursion tree grows quickly.

That is why the naive recursive solution has exponential behavior in the worst case.

Memoization Fixes the Main Problem

The natural improvement is to cache results by (i, j):

1from functools import lru_cache
2
3
4def edit_distance(a, b):
5    @lru_cache(maxsize=None)
6    def dist(i, j):
7        if i == 0:
8            return j
9        if j == 0:
10            return i
11
12        if a[i - 1] == b[j - 1]:
13            return dist(i - 1, j - 1)
14
15        return 1 + min(
16            dist(i, j - 1),
17            dist(i - 1, j),
18            dist(i - 1, j - 1),
19        )
20
21    return dist(len(a), len(b))
22
23
24print(edit_distance("kitten", "sitting"))

This keeps the recursive structure that Skiena emphasizes while reducing the number of unique subproblems to (m + 1) * (n + 1).

Relationship to Dynamic Programming

Memoized recursion and bottom-up dynamic programming solve the same subproblems. The difference is evaluation order:

• top-down recursion solves only the states it reaches
• bottom-up DP fills the table systematically

For edit distance, the bottom-up table is often easier to debug and usually avoids Python recursion-depth limits. But the recursive form is excellent for understanding the recurrence itself.

Common Pitfalls

• Presenting the plain recursive version as efficient for large strings. It is not.
• Forgetting the base cases when one prefix length becomes zero.
• Confusing insert, delete, and substitute transitions.
• Using recursion in Python for very large inputs without memoization.
• Thinking memoization changes the algorithmic idea. It keeps the same recurrence and just avoids repeated work.

Summary

• Skiena's recursive edit-distance algorithm follows the Levenshtein recurrence directly.
• The base cases handle empty prefixes, and mismatches branch into insert, delete, and substitute.
• The plain recursive form is conceptually clean but exponentially slow.
• Memoization turns it into an efficient top-down dynamic programming solution.
• For practical use, choose memoization or bottom-up DP rather than raw recursion alone.