# 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 <- len (v)  2.n <-  len (w)  3.substitutions = [] #array to save substitutions   4.if m != n:  5.  return "v and w are not equivalent"  6.else  7.for i <- m to 1 <-1 do  8.  for j <- n to j <- 1 do  9.    if v[i] != w[j]:  10.           substituted_word <- 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”)  `` Posted on Categories proxies