Is my recursive algorithm for Equivalent Words correct? Here is my problem.
Problem
Given two words and a dictionary, find out whether the words are equivalent.
Input: The dictionary, D (a set of words), and two words v and w from the dictionary.
Output: A transformation of v into w by substitutions such that all intermediate words belong to D. If no transformation is possible, output “v and w are not equivalent.”
I need to write both recursive and dynamic programming algorithm. As for recursion, I came up with this algorithm. Is it correct?
 EquivalentWordsProblem(v, w, D)
 1.m &lt;- len (v)
 2.n &lt;-  len (w)
 3.substitutions = [] #array to save substitutions 
 4.if m != n:
 5.  return &quot;v and w are not equivalent&quot;
 6.else
 7.for i &lt;- m to 1 &lt;-1 do
 8.  for j &lt;- n to j &lt;- 1 do
 9.    if v[i] != w[j]:
 10.           substituted_word &lt;- v[1…i-1]+v[j] #we substitute v[i] for w[j]
 11.              if substituted_word in D:
 12.                substitutions.append(substituted_word)
 13.                   return EquivalentWordsProblem(v[1…m-i], w, D) #recur on the string of length m - i
 14.   else:
         return EquivalentWordsProblem(v[1…m-1], w, D) #recur on the string decreasing its length by 1
 15.if len(substitutions) != 0:
 16.  return substitutions 
 17.else
 18.   return (“v and w are not equivalent”)
Your algorithm is not correct.
Here is a counterexample: $D$ contains the words $aa,bb,ac,bc$; $v=aa$; and $w=bb$.
A transformation is possible $(aa \to ac \to bc \to bb)$ but your algorithm won't find it.