I'm going to focus on implementing the recursion.
First, let's avoid the globals. The easiest way is to keep the same structure, but move it into a local namespace:
def transform(english_words, start, end):
potential_ans = [start]
results = []
def recursion(start_, end_):
if start_ == end_:
results.append(list(potential_ans))
return
for w in english_words:
if is_diff_one(w, start_) and w not in potential_ans:
potential_ans.append(w)
recursion(w, end_)
potential_ans.pop()
recursion(start, end)
return results
english_words = set(['damp', 'camp', 'came', 'dame', 'lame', 'lime', 'like'])
for answer in transform(english_words, 'damp', 'lame'):
print(answer)
I've mainly just made transform a function sets up the right arrays, and then converted the original implementation into the nested function recursion. Notice I've created a results array for storing the results. Also notice the need to make a copy of the potential answer when storing it as a result, since we will continue to modify potential_ans.
I've also modified the list of words so there is more than one result.
I assume you want to obtain all answers; it shouldn't be hard to modify this to end the recursion as soon as an answer is discovered... however, a better approach will be described below.
Given this change, the arguments to recursion are redundant: it can be changed to the following. (if you're really serious, you should profile this change, to determine whether it actually makes things faster)
def transform(english_words, start, end):
potential_ans = [start]
results = []
def recursion():
tail = potential_ans[-1]
if potential_ans[-1] == end:
results.append(list(potential_ans))
return
for w in english_words:
if is_diff_one(w, tail) and w not in potential_ans:
potential_ans.append(w)
recursion()
potential_ans.pop()
recursion()
return results
Now, a better way to generate a sequence of results is to, well, use a generator:
def transform(english_words, start, end):
potential_ans = [start]
def recursion():
tail = potential_ans[-1]
if potential_ans[-1] == end:
yield list(potential_ans)
return
for w in english_words:
if is_diff_one(w, tail) and w not in potential_ans:
potential_ans.append(w)
yield from recursion()
potential_ans.pop()
yield from recursion()
english_words = set(['damp', 'camp', 'came', 'dame', 'lame', 'lime', 'like'])
for answer in transform(english_words, 'damp', 'lame'):
print(answer)
Note the use of yield and yield from for yielding results. Using generators has a number of advantages including: you get to see results as they're created, you can stop iterating when you're happy with a result, rather than having to wait for the entire recursion to finish, you don't waste memory/time creating a list of all the results.
Generators take a little bit of time to get used to, but they're well worth it, and should often be preferred to returning lists of results.
Finally, one last neat trick; the general pattern of "make a change ... do stuff... undo the change" can be error prone; it can be easy to forget to undo the change, or an odd code path (e.g. an exception) skips the change.
The other answers suggest making copies; however, backtracking algorithms like this can often suffer massive performance penalties from such a change, so it's worth knowing a pattern that mitigates this problem without introducing copies.
We can use a context manager to do this automatically, such as below. (this post is not meant to be a tutorial on context managers)
from contextlib import contextmanager
def transform(english_words, start, end):
potential_ans = [start]
@contextmanager
def push(word):
potential_ans.append(word)
yield
potential_ans.pop()
def recursion():
tail = potential_ans[-1]
if potential_ans[-1] == end:
yield list(potential_ans)
return
for w in english_words:
if is_diff_one(w, tail) and w not in potential_ans:
with push(w):
yield from recursion()
yield from recursion()
Finally, one may dislike the fact that useful functionality is buried in nested functions; we can pull the nested functions out:
@contextmanager
def temp_push(seq, ele):
seq.append(ele)
yield
seq.pop()
def transform_recursion(english_words, end, potential_ans):
tail = potential_ans[-1]
if potential_ans[-1] == end:
yield list(potential_ans)
return
for w in english_words:
if is_diff_one(w, tail) and w not in potential_ans:
with temp_push(potential_ans, w):
yield from transform_recursion(english_words, end, potential_ans)
def transform(english_words, start, end):
yield from transform_recursion(english_words, end, [start])
w not in potential_answill be expensive if you ever test very long chains. Consider putting an upper bound on this length, or instead using a different data type that acts like both alistand aset, such as the "ordered set recipe". – Hurkyl 19 hours ago